[자료구조] 3. Graph : MST, 최단거리, Union-Find

0. Graph

노드들과 그 노드들을 연결한 간선에 대한 정보를 저장하는 자료구조

 

 

1. Terminology

1) vertex(정점), edge(간선)

2) degree : 한 정점에 간선으로 연결된 정점 개수

   2-1) in-degree : 방향 그래프에서 한 정점으로 들어오는 간선 개수

   2-2) out-degree : 방향 그래프에서 한 정점에서 나가는 간선 개수

3) Simple Path : 경로 내 중복되는 정점이 없는 경로

 

1) Ordered/unOrdered : 간선의 방향 유무

2) Weighted : 간선에 가중치 유무

3) Connected/Disconnected : 그래프 내 한 정점에 대해서 나머지 정점으로의 경로 존재 유무

4) Cycle/Acycle : 시작점과 도착점이 동일한 Simple Path의 존재 유무

5) Complete : 그래프의 모든 정점 간에 모두 간선이 있는 경우

 

cf) Complete Graph의 간선 개수는 Ordered/UnOrdered에 따라 알 수 있다.

 

 

 

2. Adjaceny List, Adjacency Matrix

// Adjacency List
vector<int> AL[N];

// Adjacency Matrix
int AM[N][M];

AL은 정점 n에 연결된 정점들을 저장하여 그래프를 표현하고

AM은 정점 n과 m 사이의 연결을 AM[n][m] = 1로 표현한다.

 

 

 

3. Spanning Tree

그래프에서 모든 정점을 포함하고 정점 간 모두 연결되면서 cycle이 없는 그래프

 

1) MST : Minimum (Cost) Spanning Tree

Spanning Tree 중 edge의 가중치 합(혹은 개수)이 가장 작은 Spanning Tree

 

2) MST algorithms

- Kruskal

모든 edge들에 대해 반복마다 최소 cost를 가진 edge를 뽑아 선택된 edge들과 cycle을 만들지 않으면 선택한다

N, E = { all edge }, T = { NULL }; // # of vertices, set of edges, set of selected edges

sort E by asc; // min heap

while( T.size < (N-1) && !E.empty ) {
	
    select edge has minimum cost in E;
    pop selected edge SE in E;
    
    if(SE makes cycle with edges in T) // using Union-Find algorithms
    	discard(SE);
    else
    	add SE to T;
}

if(T.size < N - 1)
	print("No MST");

- 시간복잡도 : O(E*logV)

E는 최대 V^2, 따라서 LogE <= 2*logV

E를 cost순으로 정렬 = O(E*logE)

Unoin-find = O(E)

 

따라서 Union-Find O(E)는 E 정렬 O(E*logE) 시간 안에 수행되므로

전체 시간복잡도는 O(E*logE) = O(E*logV)

 

 

- Prim

시작 정점을 하나 선택한 뒤, 선택된 정점 집합으로부터 뻗어나갈 수 있는 최소 비용 edge를 탐색하고 저장한다.

N, T = { all edge }; // # of vertex, set of selected edges
ST = {NULL}, TV = {0}; // selected vertices(start with 0 or other one)

sort T by asc // min heap

while(T.size < (N-1)){
	
    find edge (u,v) that u is in TV, v isn't in TV and has minimum cost in T
    
    if(there is no (u,v) such that)
    	break;
    
    add v to TV
    add (u,v) to ST
}

if(T.size < (N-1))
	print("No MST")

- 시간복잡도 : O(E*logV)

Kruskal과 같은 맥락

 

 

4. 최단 경로

1) Dijkstra

하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘

음의 가중치는 다루지 못한다.

 

매 반복마다 선택된 vertex들로부터 가장 작은 cost를 가진 새로운 vertex를 선택하고 추가한다.

그리고 새로 선택된 vertex를 포함하여 시작점부터 현재까지 선택된 모든 vertex까지의 거리를 갱신한다.

N, AL, D[N]; // # of vertices, Adjacency List, set of edges, cost from starting vertex
pq; // priority_queue that has element {current vertex, cost from starting v to current v} sorted by cost

init D[N] to INF
insert starting vertex into pq
D[starting vertet] = 0

while(!pq.empty){
	
    select element e from top of pq
    pop pq
    
    if(D[E.vertex] < e.cost) // already updated
    	continue;
        
    if(cost D[n] > from E.vertex to vertex n){ // using AL
    	update D[n]
        add {n, D[n]} to pq
    }
}

- 시간복잡도

위와 다르게 pq 대신 선형 자료구조를 쓸 경우 O(N^2)

 

pq를 쓸 경우 O(E*logN)

A. 한 정점에 대해 모든 간선 검사 O(E)

B. pq에 저장되는 원소 최대 O(E) * pq 원소 추가/삭제 O(logE) = O(E*logE) = O(E*logV)

 

참고

wordbe.tistory.com/entry/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[최단경로] 다익스트라(Dijstra) 알고리즘

 

2) Bellmanford

음의 가중치에 대한 사이클을 처리할 수 있는 알고리즘

N, E[N][N], AL // # of vertices, weight of edge between i, j, adjacency list
D[N] // distance from starting v to n

init AL using E

init D[N] with INF
D[starting v] = 0

for i=1 to N-1 // N-1번의 루프에 걸쳐 각 정점이 i+1개 정점을 거쳐오는 최단경로 갱신
	for j=1 to N // 각 정점
    	for k=1 to AL[j].size // 현재 정점과 연결된 edge에 대해
        	update D[AL[j].vertex]
            
for j=1 to N // update one more
	for k=1 to AL[j].size
        	if updatig D[AL[j].vertex] occurs
            	print("It has Negative cycle");

- 시간복잡도 O(EV)

모든 정점의 개수만큼 모든 edge를 탐색

 

- 정당성

시작점부터 임의의 정점까지의 최단경로가 위와 같다고 하면, 마지막 정점으로의 최단경로를 알기 위해서는 마지막 정점 이전의 정점까지의 최단경로를 알아내야 한다. 만약 이를 알고 있다면, 그래프 내의 모든 간선에 대해 2번을 수행 하는 것으로 마지막 정점으로의 최단경로를 갱신해줄 수 있다(마지막 이전 정점의 최단경로와 마지막 이전 정점과 마지막 정점을 잇는 간선의 경로 합은 최단경로라고 가정했기 때문이다.) . 시작점 자체는 최단경로임이 보장되기 때문에(음수 사이클이 없으므로) 귀납적으로 임의의 최단경로를 구하기 위해서는 (그 최단경로의 전체 정점 - 1)회의 1, 2번 과정을 수행하면 최단경로를 구할 수 있음을 알 수 있다.

출처: https://cloge.tistory.com/27

Shortest Path Algorithm - Bellman-Ford

 

 

참고

m.blog.naver.com/kks227/220796963742

벨만 포드 알고리즘(Bellman-Ford Algorithm) (수정: 2020-07-10)

 

3) Floyd-Wharshall

모든 최단 경로를 구하는 알고리즘

음의 가중치에 대한 사이클을 처리할 수 있는 알고리즘 

N, D[N][N], P[N][N] // # of vertices, distance from i to j, processor of j in route i to j

for i=1 to N
for j=1 to N
for k=1 to N
	if(cost from j to k > (cost from j to i + cost i + k)){
		update D[j][k]
		update P[j][k] to i
	}

- 시간복잡도 O(V^3)

 

 

 

5. Activity Network

 

 

cf. Union-Find

집합을 관리하는 자료구조로써 disjoint-set을 형성한다.

 

V = { 0, 1, 2, ... } 일때 같은 집합임을 (보통 같은 set의 가장 낮은 수로) parent로 표현한다.

 

ex)

P[2] == 1, P[5] == 1 이면 같은 집합

P[2] == 1, P[5] == 2 이면 같은 집합, 및 P[5] = 1로 갱신