신장 트리1

• 

  [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) 신장 트리(Spanning Tree) 신장 트리는 연결 그래프의 부분 그래프이다. 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리이고, 모든 노드는 적어도 하나의 간선에 연결이 되어있어야 한다. 또한 이름에서 알 수 있듯이, 트리이므로 사이클이 존재해서는 안된다. 연결 그래프이므로, DFS(깊이 우선 탐색), BFS(너비 우선 탐색)를 이용하여 구현이 가능하다. 이 때 연결 그래프에는 하나의 신장트리 뿐만이 아닌 다양하게 존재할 수 있다. 이와 같은 연결 그래프가 있을 때, 나올 수 있는 신장 트리는 다음과 같다. 최소 신장 트리(Minimum Spanning Tree) 위에서 신장 트리에 대해 알아보았다. 그래프의 간선에 가중치가 있다면, 그것을 가중치 그래프라고 한다. 가중치 무방향 그래프에.. Algorithm 2022. 7. 21.