그래프 관련 알고리즘

< 최소 신장 트리 >

 

- 신장 트리 : 순환이 없는 트리

> 깊이 우선 탐색(DFS : Depth-First Search) -> 깊이 우선 신장 트리(Depth First Spanning Tree)

> 넓이 우선 탐색(BFS : Breadth-First Search) -> 넓이 우선 신장 트리(Breadth First Spanning Tree)

 

- 최소 신장 트리 : 가중치의 합이 최소인 신장트리

 

- Kruskal Algorithm

> 그래프의 모든 간선을 비용 순으로 정렬한 뒤 낮은 비용을 가지는 순환시키지 않는 간선을 선택

 

1) 모든 간선을 가중치 값에 따라 오름 차순으로 정렬

2-1) 가장 가중치가 작으면서 순환을 발생시키지 않는 간선 추출, 순환시 해당 간선 제외

2-2) 그래프의 모든 노드가 연결될 때까지 2-1 반복

 

- Prim Algorithm

> 트리를 확장시켜 최소 비용 신장트리를 만듦

 

1) 그래프에서 임의 시작 노드를 선택하여 연결된 노드의 집합에 넣음

2-1) 연결된 노드의 집합안의 노드의 간선 중 

가중치가 가장 작으면서 순환을 발생 안하는 간선을 선택하여 연결된 노드의 집합을 확장

2-2) 그래프의 모든 노드가 연결 될때까지 2-1 반복

 

< 최단 경로 >

 

- 종류

> 단일 시작점에서 최단 경로 구하기

> 모든 최단 경로 구하기

> 도달 가능성 구하기

 

- Dijkstra Algorithm (단일 시작점에서 최단 경로)

1) 시작 노드에서 다른 노드 사이의 거리 초기화, 연결되지 않으면 ∞으로 둠

2-1) 아직 탐색 안한 노드 중 가장 인접한 노드(v)를 선택하여 최단 거리를 조사하고 거리 정보 갱신

if(yv + vw < yw)    // 거쳐가는 거리가 기존 거리보다 작으면 거리 갱신

y = yv + vw

2-2) 모든 노드를 탐색할 때까지 2-1 반복

 

- Floyd Algorithm (모든 최단 경로)

1) 그래프의 노드간 가중치에 대해 2차원 배열로 정리, 서로 인접 안하면 ∞

2)

for(v:G의 모든 노드)

for(r:G의 모든 노드)

for(s: G의 모든 노드)

if( A[r][v] + A[v][s] < A[r][s] )    // v를 거쳐가는 거리가 더 짧으면 r에서 s로 가는 거리 갱신

A[r][s] = A[r][v] + A[v][s]