12-2 그래프의 순회와 신장 트리

1. 그래프의 순회

① 그래프 순회, 탐색

- 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산

② 깊이 우선 탐색

-  시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면,

가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 반복하여 모든 정점을 방문하는 순회 방법

- 후입선출 구조의 스택 사용

③ 너비 우선 탐색

- 시작 정점에서 인접한 정점을 모두 차례로 방문하고나서 방문했던 정점에서부터 다시 인접한 정점을 차례로 방문하는 방식

- 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회방법 -> 큐 사용

 

2. 신장트리

① 신장트리

- n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로

사이클 없는 단순한 연결 그래프

 

3. 최소 비용 신장 트리

① 최소 비용 신장 트리

- 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

 

② 크루스칼 알고리즘1

- 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법'

- 간선의 수가 n-1되면 멈춤.

- 단절되면 안되고 내림차순으로 진행.

 

③ 크루스칼 알고리즘2

- 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법'

- 간선의 수가 n-1되면 멈춤.

- 사이클이 되면 안되고 오름차순으로 진행

 

④ 프림 알고리즘

- 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법