그래프는 노드(정점)과 이들을 연결하는 간선으로 구성된 자료구조이다.
방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉘며, 간선에 가중치(Weight)가 있을 수 있다.
그래프 알고리즘
최단 경로 탐색 알고리즘
- 다익스트라 알고리즘(Dijkstra's Algorithm)
- 벨만-포드 알고리즘(Bellman-Ford Algorithm)
모든 쌍 최단 경로
- 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
최소 신장 트리(MST)
- 크루스칼 알고리즘(Kruskal's Algorithm)
- 프림 알고리즘(Prim's Algorithm)
1. 다익스트라 알고리즘 (Dijkstra's Algorithm)
- 가중치가 있는 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘이다.
- 음의 가중치가 있는 경우 사용할 수 없으며, 그리디 알고리즘과 동적 계획법이 합쳐진 형태다.
- 출발 정점에서 가장 가까운 정점을 찾고, 이 정점을 경유하여 다른 정점으로 가는 거리가 더 짧은지 검사하며 작동한다.
동작 방식
방문하지 않은 정점 중 최단 거리 선택을 기반으로 하는 알고리즘
방문하지 않은 모든 정점 중에서 최단 거리를 고려해 정점을 방문
- 시작 정점과 종료 정점을 설정하여 최단 거리 테이블을 초기화한다.
- 현재 위치한 정점의 인접 정점 중에서 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 선택해 방문 처리 한다.
- 해당 정점을 거쳐 다른 정점으로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
- 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
- 가중치가 음수인 간선에도 올바르게 작동한다. 하지만 음수 가중치 순환은 처리할 수 없고 존재 여부만 확인 가능하다.
- 모든 간선을 일정 횟수 반복해서 검사함으로써 최단 경로를 찾습니다.
동작 방식
모든 정점 간의 최단 거리 선택을 기반으로 하는 알고리즘
매 단계에서 모든 간선을 전부 확인하며 모든 정점에 대해 최단 거리를 고려해 방문
- 시작 정점부터 정점과 연결된 모든 간선을 탐방하면서 거리 데이터를 갱신한다.
- 다음 정점과 연결된 모든 간선을 탐방하면서 데이터를 갱신한다.
- (vertex - 1)번 반복하여 모든 간선을 하나씩 확인한다.
- 다음 정점의 다음 정점과 연결된 모든 간선을 탐방하면서 데이터를 갱신한다.
3. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
- 가중치가 있는 그래프의 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘이다.
- 동적 프로그래밍 기법을 사용하며, 음수 가중치가 있는 간선을 포함하는 그래프에서도 작동하지만, 음수 가중치 순환은 처리할 수 없다.
동작 방식
모든 정점에서 모든 정점까지의 최단 거리 선택을 기반으로 하는 알고리즘
각 정점을 거치며 다른 정점으로 가는 모든 경로를 고려해 최단 거리를 갱신
- 2차원 배열을 각 정점 사이의 가중치로 데이터를 초기화한다. 가중치가 없는 경우 무한대로 설정한다.
- 모든 정점에 대하여 시작 정점과 끝 정점의 가능한 모든 조합을 탐색하여 최단 거리를 계산한다.
- 계산된 정점 간 거리가 기존 거리보다 짧다면 배열 데이터를 갱신한다.
4. 크루스칼 알고리즘 (Kruskal's Algorithm)
- 가중치가 있는 연결 그래프에서 최소 신장 트리를 찾는 알고리즘이다.
- 그리디 알고리즘의 일종으로, 가장 가벼운 가중치를 가진 간선부터 차례대로 선택하며 신장 트리를 구성한다.
- 선택 과정에서 사이클이 형성되는 간선은 제외한다.
동작 방식
간선 선택을 기반으로 하는 알고리즘
이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선을 선택
- 그래프의 모든 간선을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선을 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 사이클이 일어나지 않을 간선 중 가중치가 가장 작은 간선
- 선택한 간선을 MST에 하나씩 추가한다.
5. 프림 알고리즘 (Prim's Algorithm)
- 가중치가 있는 연결 그래프에서 최소 신장 트리를 찾는 알고리즘이다.
- 시작 정점을 선택하고, 선택된 정점 집합에 인접한 간선 중 최소 가중치를 가진 간선을 선택하여 트리를 확장한다.
- 크루스칼 알고리즘과 마찬가지로 사이클을 형성하는 간선은 제외한다.
동작 방식
정점 선택을 기반으로 하는 알고리즘
이전 단계에서 만들어진 신장 트리를 확장
- 시작 정점을 MST에 포함시킨다.
- MST에 포함된 정점에 인접한 정점들 중 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
- 가장 낮은 가중치를 먼저 선택한다.
- MST가 (n-1)개의 간선을 가질 때 까지 반복한다.
참고
알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘)
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란
