그래프 (2)

[출처]book.naver.com/bookdb/book_detail.nhn?bid=10896666

C로 배우는 쉬운 자료구조

목차

01 그래프의 구조 & 용어

02 그래프 순회

03 신장 트리 & 최소 비용 신장 트리

​

​

​

03. 신장 트리 & 최소 비용 신장 트리

◆ 신장트리 : 모든 정점이 n개인 무방향 그래프 G에서,

정점 n개, 간선이 (n-1)개인 트리 형태인 부분 그래프

간선을 최소로 이용해 모든 정점을 연결한 그래프

▶ 깊이 우선 신장 트리 : 깊이 우선 탐색을 이용하여 생성된 신장트리

前 포스팅에서 깊이 우선 탐색한 그래프의 탐색경로

​

▶ 너비 우선 신장 트리 : 너비 우선 탐색을 이용하여 생성된 신장트리

前 포스팅에서 너비 우선 탐색한 그래프의 탐색경로

​

​

​

◆ 최소 비용 신장 트리 : 가중치 합이 최소인 신장트리

· 가중치 그래프에서 간선에 주어지는 가중치 = 비용, 거리, 시간 등

· 무방향 가중치 그래프에서 신장 트리 비용 = 간선 (n-1)개의 가중치를 합한 값

​

▶ 크루스칼 알고리즘

Ⅰ. 가중치 높은 간선 제거 → 최소 비용 신장 트리 완성

ⅰ) 모든 간선 → 내림차순으로 정렬

간선 수 : 10개

 

ⅱ) 가중치 가장 높은 간선 제거

( ※ 정점을 그래프에서 분리시키는 간선 → 제거 X , 그 다음으로 가중치 높은 간선 제거 )

간선 ( B,C ) 제거

 

ⅲ) 간선이 (n-1)개 남을 때까지 반복

남은 간선 수 : 8개

남은 간선 수 : 7개

남은 간선 수 : 6개

​

ⅳ) 간선이 (n-1)개 되면 완성

완성된 최소 비용 신장 트리

​

​

​

Ⅱ. 가중치 낮은 간선 삽입 → 최소 비용 신장 트리 완성

ⅰ) 모든 간선 → 오름차순으로 정렬

간선 수 : 10개

ⅱ) 가중치 가장 낮은 간선 삽입

( ※ 사이클 형성하는 간선 → 삽입 X , 그 다음으로 가중치 낮은 간선 삽입 )

ⅲ) 삽입한 간선의 수가 (n-1)개 될 때까지 반복

​

삽입한 간선의 수 : 2개

삽입한 간선의 수 : 3개

삽입한 간선의 수 : 4개

삽입한 간선의 수 : 5개

삽입한 간선의 수 : 6개

​

ⅳ) 간선이 (n-1)개 되면 완성

완성된 최소 비용 신장 트리

​

​

▶ 프림 알고리즘

- 크루스칼 알고리즘처럼 미리 간선 정렬 X

하나의 정점에서 시작 → 트리 확장

​

ⅰ) 시작 정점 선택

정점 C 선택

 

ⅱ) 선택한 정점에 부속된 모든 간선 中 가중치 가장 낮은 간선 연결

간선 ( A, C ) 선택

 

ⅲ) 이전에 선택한 정점 & 새로 확장한 정점에 부속된 모든 간선 中 가중치 가장 낮은 간선 삽입

( ※ 사이클 형성하는 간선 → 삽입 X , 그 다음으로 가중치 낮은 간선 삽입 )

간선 (A, B) 선택

 

ⅳ) 간선이 (n-1)개 삽입될 때까지 반복

연결된 간선 : 3개

연결된 간선 : 4개

연결된 간선 : 5개

연결된 간선 : 6개

​

​

ⅴ) 간선이 (n-1)개 되면 완성

​

​

​

◆ 최단거리 : 신장 트리가 아닌 가중치 그래프(네트워크)에서 정점 u와 정점 v를 연결하는 경로 中 가중치의 합이 최소인 경로

- 가중치 입접 행렬 : 가중치 그래프의 가중치 저장, 2차원 배열

두 정점 사이에 간선 無 → 0 (X), ∞ (O)

자기 자신과 이어진 간선 허용 X → 대각선 값 = 0

가중치 방향 그래프 & 가중치 인접 행렬

 

​

▶ 다익스트라 최단 경로 알고리즘

- 정점 하나를 출발점, 다른 모든 정점을 도착점으로 하는 단일점에서의 최단 경로 알고리즘 中 하나로, 가장 많이 사용됨

- 무방향 그래프나 방향 그래프에 모두 적용 가능

- 원리 : 시작 정점 v에서 가장 가까운 정점 선택해 추가 → 추가된 새로운 정점에 의해 단축되는 경로 있으면 경로 거리 수정 → 반복

​

출처 : 위키백과

 

distance[w] ← min(distance[w], distance[u]+weight[u][w])

​

​

▶ 플로이드 최단 경로 알고리즘

- 모든 정점 사이의 최단 경로를 구함 → k-최단경로

- An-1[v][w] : 정점 0 ~ (n-1)까지의 모든 정점 이용한 최단경로

- 원리 : 정점 0~(n-1)까지의 정점을 고려한 최단 거리 Ak-1 구하기 → 다음 정점 k 고려할 때, Ak-1[v][w]와 Ak-1[v][k]+Ak-1[k][w] 중 작은 값 따라 최단경로 수정

​

Ak[v][w]←min(Ak-1[v][w], Ak-1[v][k]+Ak-1[k][w])