Spanningtree
-
Spanning TreeC 자료구조/Graph 2020. 10. 15. 21:51
0. 참고 문헌 1. 개념 신장 트리( Spanning tree )란 그래프 내의 모든 정점을 포함하는 트리이다. 신장 트리는 트리의 특수한 형태이므로, 모든 정점들이 연결되어 있어야 하고, 또한 사이클을 포함해서는 안 된다. 따라서, 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 그래프에서 신장 트리를 찾으려면 깊이 우선 탐색이나 너비 우선 탐색을 사용할 수 있다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 여기서는 깊이 우선 탐색 방법을 사용한다. 아래에 하나의 그래프가 주어졌다고 가정하자. 아래의 그림들은 모두 위의 그래프에서 시작정점을 바꾸어 가면서 깊이 우선 탐색 혹은 너비 우선 탐색을 해서 만든 신장 트리의 일부이다. 첫 번째 신장 트리 그래프..