그래프 이론 관련 알고리즘 정리

프로그래밍 문제를 풀면서, 묵시적인 그래프 구조를 요구하는 문제들이 많이 보여 이 기회에 정리해야 겠다는 생각이 들었다. 

먼저 묵시적인 그래프 구조라는건 무엇을 말하는걸까 굳이 그래프라고 언급하지 않아도 그래프로 추상화하여 풀 수 있는 문제들이 많다.

대표적으로, 최단거리, 최소 시간 등등의 키워드가 나오면 그래프로 추상화 해볼 수 있다. 이 때, 입력받는 형식은 1차원 혹은 2차원 배열의 형식으로 저장하게 될텐데 이를 추상화한다.

추상화하는 방식에도 종류가 있다.

1. 인접 행렬
   • 2차원 배열 형태로 간선 여부를 표현한다. 주로 boolean 타입 혹은 int 타입으로 표현하며, fully connected가 아니라면 메모리 공간의 낭비가 생길 수 있다.
   • e.g. bool adj[100][100]
2. 인접 리스트
   • 연결 리스트 자료구조를 사용하여 다이나믹하게 간선을 표현한다. 주로 vector와 같은 STL을 사용한다.
   • e.g. vector<pair<int, int>> adj[MAX_V] //연결된 정점, 간선의 가중치, 인덱스 = 현재 정점
     adj[1] => 1번 정점과 연결된 정점, 가중치 쌍의 vector

이제 그래프로 추상화했으니, 관련 알고리즘도 살펴보자

1. BFS
   • 유명한 알고리즘이기 때문에 동작 방식은 생략하고, 주요한 개념만 살펴보면 다음과 같다.
     • BFS는 가중치가 적용된 그래프에서는 최단거리를 알 수 없다.
     • 한 번 탐색한 정점을 다시 탐색할 수 있다.
2. DFS
   • 유명한 알고리즘이기 때문에 동작 방식은 생략하고, 주요한 개념만 살펴보면 다음과 같다.
     • 기저 사례와 탐색방법을 먼저 정하고 접근하자
3. 다익스트라
   • 한 정점과 다른 정점들 간의 최소비용을 구할 때 사용된다.
   • 일반적으로 모든 정점들과 연결된 간선을 탐색하기 때문에 O(VE)의 복잡도를 갖지만, 우선순위 큐를 사용하면, O(VlogE)의 복잡도로 탐색할 수 있다.
   • 단점 : 음의 가중치를 갖는 구조에선 사용할 수 없다. 최소 가중치를 우선하여 탐색하는 Greedy한 알고리즘이기 때문이다.
4. 벨만포드
   
   • 다익스트라의 문제를 보완한 알고리즘이다. 음의 가중치를 갖는 구조에서도 정상 동작한다.
   • 단, 음의 가중치를 갖는 사이클이 있다면, 동작하지 않으며 이를 발견할 수 있는 방법도 존재한다.
   • O(V^2)의 복잡도를 갖는다.
5. 플로이드 와샬
   • 모든 정점, 간선들 간의 쌍으로 최소비용을 알고 싶을 때 사용된다.
   • O(V^3)의 복잡도를 가지며, 가장 느린 속도이다.