[자료구조] 11. 그래프(2)

1. 최소비용 신장트리(MST: Minimum Spanning Tree)
   • 신장트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리 (사이클 x)
   • 최소비용 신장트리(MST): 모든 정점들을 가장 작은 비용으로 연결하는 트리
2. Kruscal의 MST 알고리즘
   : 모든 edge를 검사하여, least-weight edge를 찾고, 그 edge가 사이클을 만들지 않으면, 추가한다.
   => 시간복잡도: O(e*log(e)), 모든 edge들의 weight를 한번에 비교하므로, 희박한 그래프에서 유리하다.
   
   • Union-Find 알고리즘: 사이클을 만드는지 검사하는 알고리즘
     1. Find: 어떤 두 노드의 root를 찾아낸다. root가 서로 다르다면, 두 노드 사이의 edge는 bridge이므로, 그 edge는 사이클을 생성하지 않는다. --> edge를 추가한다.
     2. Union: edge가 추가된 두 노드는 이제 하나의 집합에 속하게 되었다. 부모노드부터 통일하여, 결국 root를 통일한다.
3. Prim의 MST 알고리즘
   : MST 집합에 인접한 정점 중에서 least-weight edge를 찾아서, 그 edge가 사이클을 만들지 않으면, 추가한다.
   => 시간복잡도: O(n^2), 이미 MST에 포함된 vertex와 연결된 edge들의 weight만을 비교하므로, 밀집한 그래프에서 유리하다.
   
   • Kruscal의 MST 알고리즘과 달리, 모든 edge들의 weight를 비교하지 않는다.
   • 모든 edge의 weight가 다르다면, 시작 node가 바뀌어도 결과는 동일하다.
   • Disconnected graph에서는 동작하지 않는다.
4. 최단경로(Shortest path)
   : 시작정점과 도착정점을 연결하는 경로 중에서, edge들의 weight 합이 최소가 되는 경로
   • MST와 달리, 최단경로에는 '시작'과 '끝'이 있다.
5. Dijkstra의 최단경로 알고리즘
   : 새로운 정점이 추가될 때마다, 그 정점과 인접한 정점까지의 distance가 업데이트될 가능성이 생긴다.
   • 하나의 시작정점에서 다른 모든 정점까지의 최단경로를 계산한다. 모든 경우의 수를 다 시도해보고 optimal을 결정하는 것이 아니다.
   • 시간복잡도: O(n^2)
6. Floyd의 최단경로 알고리즘
   : 모든 정점사이의 최단경로를 찾는다. 중간에 정점 k를 거칠 때와 거치지 않을 때의 weight를 비교하여, 최단경로를 새롭게 업데이트할지를 결정한다. 
   • 모든 정점에서 다른 모든 정점까지의 최단경로를 계산한다. 모든 경우의 수를 다 시도해보고 optimal을 결정한다.
   • 시간복잡도: O(n^3)
7. 위상정렬(Topological sorting)
   • 방향그래프(DAG: Directed Asyclic Graph): edge <u, v>가 있다면, 정점 u는 정점 v를 선행한다.
     
     1. 선행정점을 가지지 않는 정점 v를 선택한다.
     2. v와 v에서 나온 모든 간선들을 그래프에서 삭제한다.