최단거리 (1) 썸네일형 리스트형 [MST] Prim & Greedy MST 중 prim알고리즘은 그리디알고리즘을 만족하는 몇 안 되는 알고리즘이다. 여기서 mst = minimum spaning tree로 최소신장트리이다. 신장트리 중 가중치의 총합이 가장 최소임을 의미한다. 특징으로는 1. 간선의 가중치의 합이 최소여야 한다. 2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1) 개의 간선만을 사용해야 한다. 노드 1번에서 가질 수 있는 간선의 수 : 2(N-1) 노드 2번에서 가질 수 있는 간선의 수 : 2(N-2) 노드 3번에서 가질 수 있는 간선의 수 : 2(N-3) 이를 모두 더하면 2(N-1 + N-2 + N-3 + .... + N-N) 2*(N^2 - (N(N+1)/2)) E = N(N-1) 이다. 이때 prim알고리즘은 현재 보이는 것 중 가장 좋은 .. 이전 1 다음
