Spanning Tree

0. 참고 문헌

<C언어로 쉽게 풀어쓴 자료구조 내용 >

 

1. 개념

신장 트리( Spanning tree )란 그래프 내의 모든 정점을 포함하는 트리이다.

신장 트리는 트리의 특수한 형태이므로, 모든 정점들이 연결되어 있어야 하고,

또한 사이클을 포함해서는 안 된다.

따라서, 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다.

그래프에서 신장 트리를 찾으려면 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있다.

하나의 그래프에는  많은 신장 트리가 존재 가능하다.

여기서는 깊이 우선 탐색 방법을 사용한다.

 

아래에 하나의 그래프가 주어졌다고 가정하자.

아래의 그림들은 모두 위의 그래프에서 시작정점을 바꾸어 가면서 깊이 우선 탐색 혹은

너비 우선 탐색을 해서 만든 신장 트리의 일부이다.

 

첫 번째 신장 트리

그래프에서 시작정점을 A로 두고, 깊이 우선 탐색할 때 만들어진 신장트리(깊이 우선 신장 트리)

두 번째 신장 트리

그래프에서 시작정점을 A로 두고, 너비 우선 탐색할 때 만들어진 신장트리(너비 우선 신장 트리)

세 번째 신장 트리

신장 트리는 깊이 우선 탐색이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다.

 

 

2. 신장 트리 알고리즘

아래의 SearchDFS함수는 앞에서 한 깊이 우선 탐색 함수이다.

아래는 알고리즘이다.

신장 트리는 그래프의 최소 연결 부분 그래프가 된다.

여기서의 최소의 의미는 간선의 수가 가장 적다는 의미. 

신장 트리의 구현은 결국 그래프의 깊이 우선 탐색 함수를 그대로 써도 된다.

 

앞에서 배운 깊이 우선 탐색을 한 번 보고 오도록 하자.

여기에 있는 내용을 모두 가지고 와서 구현할 것이다.

designatedroom87.tistory.com/36?category=873892

Graph DFS with Recursion

 

3. 구현

위의 SpanningTree를 만드는 함수는 깊이 우선 탐색 함수와 내용이 같다.

 

메인 함수

메인 함수에서 위의 처음에 주어진 트리와 같이 설정을 했다.

 

프로그램 실행결과

 

소스 파일

common.h

0.00MB

Graph.c

0.00MB

Graph.h

0.00MB

main.c

0.00MB