빠르게 성장하는 개발자

신장트리: n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리MST (Minimum Spanning Tree): 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim 알고리즘Kruskal 알고리즘Dijkstra 알고리즘첫 번째로 Prim 알고리즘에 대해서 알아보려고 한다. 1. Prim 알고리즘의 기본 원리하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 나간다.임의 정점을 하나 선택해서 시작한다.선택한 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 간선을 선택한다.모든 정점이 선택 될 때까지 1~2를 반복한다. 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지한다.트리 정점들(tree vertices) :..