1. 벨만 포드 알고리즘(Bellman-Ford) 다익스트라는 한 시작점의 최단 거리들을 구하는 알고리즘이지만 음수 간선이 있는 경우 정당성이 보장되지 않는다. 벨만 포드 알고리즘은 다익스트라 알고리즘과 똑같은 단일 시작점 최단 경로 알고리즘이다. 이것은 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며, 음수 사이클의 여부 또한 알 수 있다. 벨만-포드 알고리즘은 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 그러므로 수행 과정에서 각 정점까지의 최단 거리의 상한을 담은 배열 upper[]을 유지해야한다. 이 값은 알고리즘이 진행됨에 따라 점점 줄어들고, 알고리즘이 종료할 때는 실제 최단 ..

1. 최단 경로 문제 (shortest path problem) : 가중치 있는 그래프 최단 경로 문제란 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제로, 그래프의 응용 문제 가운데 가장 유용하고 널리 사용된다. 가중치가 없는 그래프에 대한 최단 경로는 BFS를 사용하면 되므로 여기서는 가중치 있는 그래프에 대한 알고리즘을 다룬다. 이 알고리즘들은 '최단 경로'를 구성하는 정점들의 목록을 구해주는 것이 아니라 '최단 경로의 길이'를 찾아 주는 것들이다. 실제 경로를 얻어내려면 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내는 코드를 작성해야한다. 다양한 그래프의 종류와 특성에 따라 알고리즘의 효율성이 달라지기 때문에 많은 경로 알고리즘이 존재한다...

1. 최단 경로 전략 너비 우선 탐색은 최단 경로 문제를 푸는 가장 직관적이고 유명한 방법이지만, 모든 최단 경로 문제를 너비 우선 탐색만으로 풀 수 있는 것은 아니다. 문제에 따라서는 너비 우선 탐색보다 다른 탐색 알고리즘이 더 강력한 경우가 있다. 2. 15- 퍼즐 7 8 4 1 2 3 5 6 9 10 11 12 13 14 15 => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 X 4 격자에 끼워진 열다섯 개의 숫자 타일을 순서에 맞게 맞추는 퍼즐이다. 빈 칸에 상하좌우로 인접한 타일 하나를 빈 칸으로 밀어넣는 것을 한번의 움직임이라 할 때, 이 퍼즐을 해결하기 위해 필요한 최소 움직임을 구하는게 오늘의 목적이다. 이 문제를 풀기 위한 첫번째 단계는 게임판의 상태를 정점으로 표..

1. 그래프의 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색은 깊이 우선 탐색과 함께 그래프 탐색 방식의 두 축을 이룬다. 다익스트라의 최단 거리 알고리즘이나 프림의 최소 스패닝 트리 알고리즘에서 BFS가 쓰인다. 너비 우선 탐색은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 이 중 처음 보는 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 이중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해둔다. 인접한 정점을 모두 검사하고 나면, 지금까지 기록한 목록에서 다음 정점을 꺼내서 방문하게 된다. 따라서 BFS의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지..

1. 간선의 분류: 유향 dfs를 수행하면 그래프의 간선을 한 번씩은 조사하게 된다. 간선의 종류는 두가지가 있다. - 처음 발견된 정점으로 연결된 간선 - 무시되는 간선 이들에 대한 정보를 수집하면 그래프 구조에 대해 많은 것을 알 수 있다. 일단 연결된 간선들만을 모아보면 트리 형태를 띠게 된다. (위 그림은 0번 정점을 루트로 하는 트리 형태) 이 트리의 이름을 그래프의 깊이 우선 탐색의 스패닝 트리 혹은 DFS 스패닝 트리 라고 부른다. DFS스패닝 트리를 생성하고 나면 모든 간선을 4가지로 분류할 수 있다. - 트리 간선(tree edge) : 스패닝 트리에 포함된 간선 - 순방향 간선(forward edge) : 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선을 말한다. 위 ..

1. 오일러 서킷 (Eulerian circuit) - 한붓 그리기 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제 이와 같은 경로를 그래프 이론에서 오일러 서킷이라고 부른다. 오일러 서킷이 어느 경우에 존재할 수 있는지를 판단하는 단서는 반대로 오일러 서킷이 존재할 수 없는 경우를 생각하는것이다. 가장 생각하기 쉬운 경우는 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우이다. (간선을 가지지 않은 컴포넌트는 예외) 정점의 차수(degree) 시작점이 u이고 끝점이 v인 특정 경로 u->v 가 모든 간선을 지나지 못하고 끝났다고 해보자. 이는 v에서 연결된 간선은 전부 한번 씩 지나갔다는 것을 의미한다. (갈곳이 없다) u != v: 항상 v는 홀수 개의 간..