MST
A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight among all the possible spanning trees.
A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that includes all the vertices of the graph.
prim's algorithm
아이디어의 핵심은 그래프를 두 가지로 나누어 생각하는 것이다.
- A: mst에 포함된 set
- B: mst에 포함되지 않은 set
MST를 만드는 중간 단계에서 A와 B를 연결하는 최선의 방법은 무엇일까?
A와B 사이 edges중 가장 최소를 연결하는 것이다.
Steps of Prim's Algorithm:
1. Initialization: Start with an arbitrary vertex and mark it as part of the MST.
2. Edge Selection: From the set of edges that connect vertices in the MST to vertices outside the MST, select the edge with the minimum weight.
3. Update: Add the selected edge and the connected vertex to the MST.
4. Repeat: Repeat the edge selection and update steps until all vertices are included in the MST.- priority_queue를 통해 후보 edges를 삽입 조회 한다.
- 힙 조회: O(logV) -> 매 정점마다 최소 한번-> O(VlogV)
- 힙 삽입: O(logV) -> edge 조사할 때마다 삽입->O(ElogV)
- 시간 복잡도는 O( (E+V)*log(V) ) 이다.
kruskal's algorithm
아이디어의 핵심은 edge의 weight에 집중하는 것이다.
edges를 오름차순으로 정렬한 후에, 짧은 것부터 MST에 필요한 것을 선택한다.
Steps of Kruskal's Algorithm:
1. Initialization: Sort all the edges in the graph by their weight in non-decreasing order.
2. Edge Selection: Starting from the smallest edge, add the edge to the MST if it doesn't form a cycle with the already included edges.
3. Cycle Detection: Use a union-find data structure to detect and prevent cycles.
4. Repeat: Continue adding edges until the MST contains exactly (V-1) edges, where V is the number of vertices.- disjoint_set 을 사용한다.
- 시간 복잡도는 O(E * log E) or O(E * log V)이다.
- Edge 정렬 시간: O(E*logE)
- find와 union 한 번: O(logV)
- 최종 시간 복잡도: 둘의 합은 O(ElogE + ElogV), 그러나 E는 최대 V^2개가 가능. 따라서 경우에 따라 최종적으로 O(E * log E) or O(E * log V)
(공간 복잡도: O(E+V) )
prim's vs kruskal's algorithm
- Dense Graph 에서는 prim's algorithm 이 좋다.
- Dense Graph: 간선 많음, E ≈ V²
- sparse Graph 에서는 kruskal's algorithm 이 좋다.
- Sparse Graph: 간선 적음, E ≪ V²
Disjoint Set algorithm
Shortest path vs MST
- shortest path: src, dst가 존재한다. src가 무엇이냐에 따라 결과가 다르다.
- mst: src, dst가 없다.
