[Date Structure] 가중치 그래프
1. 가중치 그래프
- 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프
- 경로의 강도 : 경로상의 모든 간선의 강도 합
2. 가중치 그래프의 표현과 구현
인접 행렬에 가중치를 저장한다. 이때 가중치의 범위를 설정해야 한다.
- 간선이 있는 경우 : 인접 행렬의 값이 0 ~ INF 사이($0 < adj[u][v] <$ INF)
- 간선이 없는 경우 : 인접 행렬의 값이 INF 이상($adj[u][v] >=$ INF)
3, 최소비용 신장트리(Minimum Spanning Tree, MST)
가선들의 가중치 합이 최소인 신장트리
최소 비용 신장트리를 구하는 방법에는 Kruskal과 Prim 알고리즘이 있다.
Kruskal의 MST 알고리즘
각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택하는 방법
- Greedy method : 어떤 결정을 해야 할 때마다 ‘그 순간에 최적’이라고 생각되는 것을 선택하는 방법
- Kruskal 알고리즘은 Kruskal 알고리즘에 대해 항상 최적의 해답을 주는 것으로 증명된 greedy method를 사용한다.
- 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
- 가중치가 가장 작은 간선 e를 뽑는다.
- e를 넣어 신장트리에 사이클이 생가면, 넣지 않고 2번으로 돌아간다.
- 사이클이 생기지 않으면, 최소 신장 트리에 삽입한다.
- n-1개의 간선이 삽입될 때까지 2번으로 이동한다.
Prim의 MST 알고리즘
하나의 정점에서부터 시작하여 트리를 단계적으로 확장해나가는 방법
- 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.
- 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다.
- 이 정점 v와 이때의 간선을 트리에 추가한다.
- 모든 정점이 삽입될 대까지 2번으로 이동한다.
Kruskal의 알고리즘은 간선을 기반으로 하는데 비해, Prim 알고리즘은 정점을 기반으로 한다.
4. 최단 경로
최단 경로 문제 : 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제
최단 경로를 구하는 구하는 방법으로는 Dijkstra와 Floyd의 두 가지 알고리즘이 있다.
Dijkstra 알고리즘
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
X에서 Z로 가는 비용 vs X에서 Y로 가는 비용 + Y에서 Z로 가는 비용
- 출발 노드를 설정한다.
- 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
- 해당 노드를 거쳐서 특정한 노드로 가능 경우를 고려하여 최소 비용을 갱신한다.
- 3번과 4번을 반복한다.
Floyd의 최단 경로 알고리즘
모든 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있는 방법
Dijkstra는 특정한 노드 한 개에서 출발하는 모든 비용을 구하는 것이기 때문에 일차원 배열을 사용하지만 Floyd는 2차원 배열을 사용하며 2차원을 배열을 계속해서 갱신하여 모든 최소 비용을 구한다.