[알고리즘 개념] 신장트리(spanning tree)

신장트리(spanning tree)

• 특징

  • 모든 정점이 연결되어 있으면서 사이클이 없는 트리이다

  • 그래프에 있는 n개의 정점을 n-1개의 간선으로 연결한다

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

  • 깊이 우선 탐색이나 너비 우선 탐색 도중 간선만 모으면 만들 수 있다

    //깊이 우선탐색을 개조한 신장트리 간선 모으기
    depth_search(v):
    		v를 방문처리
    		for u in (v에 인접한 정점 == u):
    				if (u가 방문되지 않았다면):
    						(v,u)를 신장 트리 간선으로 표시;
    						depth_search(u);

  • 신장 트리는 통신 네트워크 구축에 많이 사용된다. 예를 들어 n개의 위치를 연결하는 통신 네트워크를 최소의 링크를 이용하여 구축할 경우 최소 링크수는 (n-1)이 된다. 따라서 신장트리를 구함으로 써 해결할 수 있다. 하지만 각 링크의 구축비용은 같지 않다. 따라서 단순히 가장 적은 링크를 사용하는 것이 아닌 간선에 붙어있는 비용까지 고려하여 최소 비용의 신장트리를 선택할 필요가 있다

최소신장트리(Minimum spanning tree MST)

• 특징
  • 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 말한다
  • 최소신장트리를 구하는 방법은 Kruskal과 Prim 알고리즘이 있다

크루스칼
프림