최소신장트리 (1) 썸네일형 리스트형 알고리즘 - 최소 신장 트리(Minimum Spanning Tree), 크루스칼(Kruskal), 프림(Prim) Python 코드 최소 신장 트리 (MST) MST : Minimum Spanning Tree 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 신장 트리 (Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 이다. 최소 연결이란, 간선의 수가 가장 적은 것이다. Spanning Tree의 특징 - DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다 - 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. - Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. MST (Minimum Spanning Tree) 그래프에서 모든 정점을 연결하되, 사이클이 존재하지 않고 간선의.. 이전 1 다음
