MST (1) 썸네일형 리스트형 최소신장트리(Minimum Spanning Tree) 최소신장트리란? 하나씩 분해하면서 살펴보자. Q. 신장트리란 ? 그래프는 각 정점과 정점간 연결된 에지의 집합임. G=(V,G). 그런 그래프중 모든 정점을 포함하고 & 정점간 서로 연결(connected)되어 있고 & 사이클(cycle)이 없는 그래프를 말한다. 트리자료구조가 바로 이 조건에 성립하고 그래서 신장트리라고 함. 그림2 에서 (a)는 무방향 그래프인이고 모든 정점간 연결되어 있으나 사이클(a-b-c, b-c-d등등)이 존재해서 신장트리가 아니다. (b), (c), (d) 는 모든 정점을 포함하고 & 정점이 서로 연결되어 있고 & 사이클이 하나도 없으니 신장트리라고 할 수 있음. 따라서 신장트리는 그래프의 부분그래프(subgraph) 라고 볼 수 있고 모든 신장트리는 정점 V 가 N개 라면 .. 이전 1 다음
