Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)

Spanning Tree

N개의 노드들의 connected graph에서 얻을 수 있음

• depth-first traversal 또는 breadth-first traversal 을 통해 확인
• N개의 node와 N-1개의 edges로 된 Tree
• cycle은 그래프로부터 제거됨 - 한번 방문한 노드는 다시 방문하지 않기에 cycle이 생길 수 없음

한개 이상의 spanning tree는 같은 그래프에서 구할 수 있음

추가정보

그래프가 connected 일 때, dfs나 bfs는 암묵적으로 그래프 G의 edge를 두개의 집합으로 분리

• T(for tree edges): edge의 집합으로 사용되거나 search 도중에 방문
• N(for nontree edges): 남아있는 edge의 집합

• T의 edge는 G의 모든 vertex들을 포함하는 트리를 형성

요약

• Spanning Tree는 G의 edge로만 구성되며 G안의 모든 vertex들을 포함하는 트리
• 다시말해, 정점집합 v를 그대로 두고 (각 점들을 움직이지 않고) 간선(link)를 v-1개(v개의 link로 연결하면 cycle이 생김)만 남겨 트리가 되도록 만든 것.

Spanning Tree의 이점

1. spanning tree에 nontree edge를 추가한다면 cycle이 됨

2. spanning tree는  V(G’) = V(G) 이고 G’는 connected 와 같은 G의 minimum 그래프 G’임

3. |E(G’)| = n - 1 이라면 |V(G)| = n 임
   
   • edge를 최소한으로 사용하므로 minimum cost spanning tree 이다.

예시

Depth-First Traversal Search

Breadth-First Traversal Search

Minimum Spanning Tree

N 개의 노드들의 weighted connected 그래프에서 얻을 수 있음

총 weighted가 최소한인 spanning tree

일반적으로 unique가 아님

minimum-cost 문제를 모델링하고 해결하는데 사용됨

어느 노드에서 시작하느냐에 따라 결과가 달라질 수 있음

추가정보

weighted undirected 그래프의 spanning tree 비용

• spanning tree 안에 있는 edge의 cost(weight)의 합
• 최소비용의 spanning tree
• Kruskal, Prim, Sollin 알고리즘이 대표
• greedy method: 단계적으로 최적의 해결책을 구성하고, 어떤 기준을 사용하여 각 단계에서 최적의 결정을 내림

spanning tree는 최소비용을 기준

• 그래프 안에 있는 edge만을 사용
• 정확하게 n-1 개의 edge를 사용
• cycle을 유발할 수 있는 edge는 사용하지 않을 수 있음

요약

• 각 연결한 link의 edge가 가장 작은 신장트리를 말한다.
• 여기에 prim's, kruskal's, sollin's algorithm이 대표적이고 이 알고리즘들은 전부 greedy method이다. greedy 방법은 현재의 상황에서 자신이 최선의 선택을 하는 방법을 사용한다.

Prim 알고리즘

1. 그래프의 node에서 시작
2. 모든 인접한 node들을 계산
3. 최소한의 edge의 weight를 선택
4. 선택된 인접한 노드에서 계속 시작
   • 선택되지 않은 모든 edge를 계산
   • 새로 인접한 모든 edge들을 계산
   • 최소한의 weight를 가진 edge를 선택. 단 cycle은 피함
5. 그래프의 모든 node들을 포함할 때까지 진행하고 모든 노드는 1번만 방문하도록 고려

추가정보

단일 vertex를 포함하는 T 라는 트리에서 시작

T ∪ {(u,v)}가 트리(cycle은 안됨)가 되도록 T의 최소비용인 edge(u,v)를 추가하고 T가 n-1 edge를 포함할 때까지 이 단계를 반복

알고리즘의 각 단계에서 선택되는 edge의 집합

• prim 알고리즘은 나무를 형성하고 kruskal 알고리즘은 숲을 형성

요약

• 어느 한 점을 선택해 해당 점에서 갈 수 있는 최소의 edge를 결정한 다음 잇는다. 이은 다음 두 점에서 갈 수 있는 최소의 edge를 다시 결정해 잇고 이러한 방식으로 모든 vertex를 이을 때 까지 한다.

예시

위와 같은 그래프를 prim알고리즘을 사용하여 탐색

B-D의 edge를 선택할 경우, cycle이 되기 때문에 선택하지 않음

예시2

위와 같은 그래프를 prim알고리즘을 사용하여 탐색

Kruskal 알고리즘

prim 알고리즘과 다르게 어느 한 vertex를 선택하지 않고 전체 link의 edge중 가장 작은 edge를 찾아 잇는다. 그 다음 가장 작은 edge를 이어가는 방식

예시

위와 같은 그래프를 kruskal 알고리즘을 사용하여 탐색

Dijkstra 알고리즘

source에서 destination 까지 최단거리는 무엇일까?

Dijkstra 알고리즘은 단일 출발지에서 그래프 이론 안에 있는 가장 짧은 경로 찾기 문제를 해결하는 알고리즘

directed와 undirected 그래프 모두 작동하지만 모든 edge는 양수의 weight를 가져야 함

접근법: greedy 알고리즘 Input: Weighted 그래프 G={E,V} 와 출발지 vertex v∈V이고 모든 edge는 양수 Output: 주어진 출발지 vertex v∈V 에서 다른 모든 vertex까지의 최단 경로 길이 (또는 최단 경로 그 자체)

출발점에서 모든 목적지까지의 가장 짧은 경로를 탐색 - greedy 알고리즘

• 양수의 edge 비용만 탐색: Dijkstra 알고리즘
• 음수를 포함한 모든 edge 비용을 탐색: Bellman-ford 알고리즘
• 모든 pair의 가장 짧은 경로 탐색 (dynamic programming): floyd 알고리즘

기본컨셉

edge가 양수인 길을 선택

(A,B) ≤ (A,C) 이므로 (A,B) 선택

(A,B,C) ≤ (A,C), (A,B,D) 이므로 (A,B,C) 선택

(A,B,D) ≤ (A,B,C,E), (A,B,C,F), (A,B,C,G) 이므로 (A,B,D) 선택

위와 같은 방법으로 A에서 모든 vertex까지의 모든 경로를 찾을때까지 반복

기본컨셉설명

1. S는 가장 짧은 경로를 가지는 v0을 포함하는 vertex들의 집합을 나타내도록 함
2. S가 아닌 w의 경우, dist[w]는 v0에서 출발해 S의 vertex들을 지나고 w로 끝나는 최단 경로의 길이라고 나타냄
3. S 안에 있지 않은 vertex u를 찾을 수 있고 dist[u]는 minimum이고 S안에 u를 추가함
4. 경로를 적절하게 유지

해당 알고리즘의 시간복잡도는 (|V|2)

예시

A 에서부터 시작

요약

• 시작점에서 모든 도착점까지 가장 짧은 path의 cost를 찾는 알고리즘.