크러스컬 (1) 썸네일형 리스트형 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)와 Kruskal, Prim 알고리즘 Spanning Tree (신장 트리) 란? Spanning Tree (신장 트리)란 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리이다. 무방향 그래프란 방향성이 없는 그래프로 그림상에서 화살표가 아닌 실선으로 이루어진 그래프를 뜻한다. 즉, Spanning Tree는 최소의 간선을 이용하여 모든 정점을 연결한 그래프이다. 너비 우선 탐색을 이용하여 생성된 신장 트리를 BFS (Breath First Spanning tree, 너비 우선 신장 트리)라고 하고, 깊이 우선 탐색을 이용해 생성된 신장 트리를 DFS (Depth First Spanning tree, 깊이 우선 신장 트리)라고 한다. Spanning tree는 최소의 도로를 이용한 도로망 건설이나 최소의 네트워크선을 이.. 이전 1 다음
