Prim의 알고리즘 소개:
우리는 논의했습니다 최소 스패닝 트리에 대한 Kruskal 알고리즘 . Kruskal의 알고리즘과 마찬가지로 Prim의 알고리즘도 그리디 알고리즘 . 이 알고리즘은 길을 따라 연결된 모든 가장자리를 탐색하기 위해 항상 단일 노드로 시작하여 여러 개의 인접한 노드를 통해 이동합니다.
알고리즘은 빈 스패닝 트리로 시작됩니다. 아이디어는 두 개의 정점 세트를 유지하는 것입니다. 첫 번째 세트에는 MST에 이미 포함된 정점이 포함되고, 다른 세트에는 아직 포함되지 않은 정점이 포함됩니다. 모든 단계에서 두 세트를 연결하는 모든 가장자리를 고려하고 이러한 가장자리에서 최소 가중치 가장자리를 선택합니다. 가장자리를 선택한 후 가장자리의 다른 끝점을 MST가 포함된 세트로 이동합니다.
그래프의 두 정점 세트를 연결하는 간선 그룹을 호출합니다. 그래프 이론의 컷 . 따라서 Prim 알고리즘의 모든 단계에서 컷을 찾고 컷에서 최소 가중치 가장자리를 선택한 다음 이 꼭지점을 MST 세트(이미 포함된 꼭지점을 포함하는 세트)에 포함시킵니다.
Prim의 알고리즘은 어떻게 작동하나요?
Prim 알고리즘의 작동은 다음 단계를 사용하여 설명할 수 있습니다.
1 단계: 임의의 정점을 MST의 시작 정점으로 결정합니다.
2 단계: MST에 포함되지 않은 정점(프린지 정점이라고도 함)이 나올 때까지 3~5단계를 수행합니다.
3단계: 트리 꼭지점과 주변 꼭지점을 연결하는 모서리를 찾습니다.
4단계: 이 가장자리 중 최소값을 찾으십시오.
5단계: 어떤 사이클도 형성하지 않는 경우 선택한 에지를 MST에 추가합니다.
6단계: MST를 반환하고 종료합니다.
메모: 사이클을 결정하기 위해 정점을 두 세트로 나눌 수 있습니다. 한 세트는 MST에 포함된 정점을 포함하고 다른 세트는 주변 정점을 포함합니다.
권장 연습 최소 스패닝 트리 시도해 보세요!Prim의 알고리즘 예시:
최소 스패닝 트리(MST)를 찾는 데 필요한 예로 다음 그래프를 고려하십시오.
그래프의 예
1 단계: 먼저 최소 스패닝 트리의 시작 정점 역할을 하는 임의의 정점을 선택합니다. 여기서는 꼭지점을 선택했습니다. 0 시작 정점으로.
0이 시작 정점으로 선택되었습니다.
2 단계: 불완전한 MST와 다른 꼭지점을 연결하는 모든 모서리는 모서리 {0, 1} 및 {0, 7}입니다. 이 둘 사이에서 최소 가중치를 갖는 간선은 {0, 1}입니다. 따라서 MST에 가장자리와 정점 1을 포함시킵니다.
MST에 1이 추가됩니다.
3단계: 불완전한 MST를 다른 정점에 연결하는 간선은 {0, 7}, {1, 7} 및 {1, 2}입니다. 이러한 간선 중에서 최소 가중치는 간선 {0, 7} 및 {1, 2}에 해당하는 8입니다. 여기에 MST에 모서리 {0, 7}과 꼭지점 7을 포함시키겠습니다. [MST에 가장자리 {1, 2}와 정점 2도 포함할 수 있었습니다].
MST에 7이 추가되었습니다.
4단계: 불완전한 MST와 주변 꼭지점을 연결하는 간선은 {1, 2}, {7, 6} 및 {7, 8}입니다. 가중치가 가장 작은(즉, 1) MST에 모서리 {7, 6}과 꼭지점 6을 추가합니다.
MST에 6이 추가되었습니다.
5단계: 이제 연결 모서리는 {7, 8}, {1, 2}, {6, 8} 및 {6, 5}입니다. 가장자리의 가중치가 최소(즉, 2)이므로 가장자리 {6, 5}와 정점 5를 MST에 포함합니다.
MST에 정점 5 포함
배열과 배열리스트의 차이점6단계: 현재 연결되어 있는 간선 중에서 {5, 2} 간선의 가중치가 가장 작습니다. 따라서 해당 가장자리와 꼭지점 2를 MST에 포함하세요.
MST에 정점 2 포함
7단계: 불완전 MST와 다른 간선 사이의 연결 간선은 {2, 8}, {2, 3}, {5, 3} 및 {5, 4}입니다. 최소 가중치를 갖는 가장자리는 가중치 2를 갖는 가장자리 {2, 8}입니다. 따라서 이 가장자리와 정점 8을 MST에 포함합니다.
MST에 정점 8을 추가합니다.
8단계: 여기에서 모서리 {7, 8}과 {2, 3} 모두 최소값인 동일한 가중치를 가짐을 확인하세요. 그러나 7은 이미 MST의 일부입니다. 따라서 우리는 가장자리 {2, 3}을 고려하고 해당 가장자리와 정점 3을 MST에 포함시킵니다.
MST에 정점 3 포함
9단계: 정점 4만 포함됩니다. 불완전 MST에서 4까지의 최소 가중치 간선은 {3, 4}입니다.
MST에 정점 4 포함
MST의 최종 구조는 다음과 같으며 MST의 edge의 가중치는 (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
위의 방법으로 형성된 MST의 구조
메모: 세 번째 단계에서 모서리 {1, 2}를 선택한 경우 MST는 다음과 같습니다.
MST에서 가장자리 {1, 2}를 선택한 경우 대체 MST의 구조
Prim의 알고리즘을 구현하는 방법은 무엇입니까?
다음 단계에 따라 활용하세요. 프림의 알고리즘 그래프의 MST를 찾기 위해 위에서 언급한 내용은 다음과 같습니다.
- 세트 만들기 mstSet MST에 이미 포함된 정점을 추적합니다.
- 입력 그래프의 모든 정점에 키 값을 할당합니다. 모든 키 값을 INFINITE로 초기화합니다. 첫 번째 정점이 먼저 선택되도록 키 값을 0으로 할당합니다.
- 하는 동안 mstSet 모든 정점을 포함하지 않음
- 정점 선택 ~에 그건 거기 없어 mstSet 최소 키 값을 갖습니다.
- 포함하다 ~에 에서 mstSet .
- 모든 인접한 정점의 키 값을 업데이트합니다. ~에 . 키 값을 업데이트하려면 인접한 모든 정점을 반복합니다.
- 모든 인접한 정점에 대해 ~에 , 가장자리의 무게 u-v 이전 키 값보다 작습니다. ~에 , 키 값을 가중치로 업데이트합니다. u-v .
키 값을 사용하는 아이디어는 다음에서 최소 가중치 가장자리를 선택하는 것입니다. 자르다 . 키 값은 아직 MST에 포함되지 않은 정점에 대해서만 사용되며, 이러한 정점의 키 값은 MST에 포함된 정점 집합에 연결하는 최소 가중치 가장자리를 나타냅니다.
다음은 접근 방식의 구현입니다.
C++
// A C++ program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> using> namespace> std;> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout << 'Edge Weight
'; for (int i = 1; i cout << parent[i] << ' - ' << i << ' ' << graph[i][parent[i]] << '
'; } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // Print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; } // This code is contributed by rathbhupendra> |
>
>
씨
// A C program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> #include> #include> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] int printMST(int parent[], int graph[V][V]) { printf('Edge Weight
'); for (int i = 1; i printf('%d - %d %d
', parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; }> |
>
>
ABS C 코드
자바
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> >// Number of vertices in the graph> >private> static> final> int> V =>5>;> >// A utility function to find the vertex with minimum> >// key value, from the set of vertices not yet included> >// in MST> >int> minKey(>int> key[], Boolean mstSet[])> >{> >// Initialize min value> >int> min = Integer.MAX_VALUE, min_index = ->1>;> >for> (>int> v =>0>; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
>
>
파이썬3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> [[>0> for> column>in> range>(vertices)]> >for> row>in> range>(vertices)]> ># A utility function to print> ># the constructed MST stored in parent[]> >def> printMST(>self>, parent):> >print>(>'Edge Weight'>)> >for> i>in> range>(>1>,>self>.V):> >print>(parent[i],>'-'>, i,>' '>,>self>.graph[i][parent[i]])> ># A utility function to find the vertex with> ># minimum distance value, from the set of vertices> ># not yet included in shortest path tree> >def> minKey(>self>, key, mstSet):> ># Initialize min value> >min> => sys.maxsize> >for> v>in> range>(>self>.V):> >if> key[v] <>min> and> mstSet[v]>=>=> False>:> >min> => key[v]> >min_index>=> v> >return> min_index> ># Function to construct and print MST for a graph> ># represented using adjacency matrix representation> >def> primMST(>self>):> ># Key values used to pick minimum weight edge in cut> >key>=> [sys.maxsize]>*> self>.V> >parent>=> [>None>]>*> self>.V># Array to store constructed MST> ># Make key 0 so that this vertex is picked as first vertex> >key[>0>]>=> 0> >mstSet>=> [>False>]>*> self>.V> >parent[>0>]>=> ->1> # First node is always the root of> >for> cout>in> range>(>self>.V):> ># Pick the minimum distance vertex from> ># the set of vertices not yet processed.> ># u is always equal to src in first iteration> >u>=> self>.minKey(key, mstSet)> ># Put the minimum distance vertex in> ># the shortest path tree> >mstSet[u]>=> True> ># Update dist value of the adjacent vertices> ># of the picked vertex only if the current> ># distance is greater than new distance and> ># the vertex in not in the shortest path tree> >for> v>in> range>(>self>.V):> ># graph[u][v] is non zero only for adjacent vertices of m> ># mstSet[v] is false for vertices not yet included in MST> ># Update the key only if graph[u][v] is smaller than key[v]> >if> self>.graph[u][v]>>0> and> mstSet[v]>=>=> False> > >and> key[v]>>self>.graph[u][v]:> >key[v]>=> self>.graph[u][v]> >parent[v]>=> u> >self>.printMST(parent)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph(>5>)> >g.graph>=> [[>0>,>2>,>0>,>6>,>0>],> >[>2>,>0>,>3>,>8>,>5>],> >[>0>,>3>,>0>,>0>,>7>],> >[>6>,>8>,>0>,>0>,>9>],> >[>0>,>5>,>7>,>9>,>0>]]> >g.primMST()> # Contributed by Divyanshu Mehta> |
>
>
씨#
// A C# program for Prim's Minimum> // Spanning Tree (MST) algorithm.> // The program is for adjacency> // matrix representation of the graph> using> System;> class> MST {> >// Number of vertices in the graph> >static> int> V = 5;> >// A utility function to find> >// the vertex with minimum key> >// value, from the set of vertices> >// not yet included in MST> >static> int> minKey(>int>[] key,>bool>[] mstSet)> >{> >// Initialize min value> >int> min =>int>.MaxValue, min_index = -1;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in parent[] static void printMST(int[] parent, int[, ] graph) { Console.WriteLine('Edge Weight'); for (int i = 1; i Console.WriteLine(parent[i] + ' - ' + i + ' ' + graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[, ] graph) { // Array to store constructed MST int[] parent = new int[V]; // Key values used to pick // minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices // included in MST bool[] mstSet = new bool[V]; // Initialize all keys // as INFINITE for (int i = 0; i key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex // First node is always root of MST key[0] = 0; parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex // from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex // to the MST Set mstSet[u] = true; // Update key value and parent // index of the adjacent vertices // of the picked vertex. Consider // only those vertices which are // not yet included in MST for (int v = 0; v // graph[u][v] is non zero only // for adjacent vertices of m // mstSet[v] is false for vertices // not yet included in MST Update // the key only if graph[u][v] is // smaller than key[v] if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] parent[v] = u; key[v] = graph[u, v]; } } // Print the constructed MST printMST(parent, graph); } // Driver's Code public static void Main() { int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); } } // This code is contributed by anuj_67.> |
>
>
자바스크립트
> // Number of vertices in the graph> let V = 5;> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> function> minKey(key, mstSet)> {> >// Initialize min value> >let min = Number.MAX_VALUE, min_index;> >for> (let v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] function printMST(parent, graph) { document.write('Edge Weight' + ' '); for (let i = 1; i document.write(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]] + ' '); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation function primMST(graph) { // Array to store constructed MST let parent = []; // Key values used to pick minimum weight edge in cut let key = []; // To represent set of vertices included in MST let mstSet = []; // Initialize all keys as INFINITE for (let i = 0; i key[i] = Number.MAX_VALUE, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first vertex. key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (let count = 0; count { // Pick the minimum key vertex from the // set of vertices not yet included in MST let u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (let v = 0; v // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver code let graph = [ [ 0, 2, 0, 6, 0 ], [ 2, 0, 3, 8, 5 ], [ 0, 3, 0, 0, 7 ], [ 6, 8, 0, 0, 9 ], [ 0, 5, 7, 9, 0 ] ]; // Print the solution primMST(graph); // This code is contributed by Dharanendra L V.> |
>
>산출
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Prim 알고리즘의 복잡성 분석:
시간 복잡도: 오(V2), 입력된 경우 그래프는 인접 목록을 사용하여 표현됩니다. , 그러면 바이너리 힙의 도움으로 Prim 알고리즘의 시간 복잡도를 O(E * logV)로 줄일 수 있습니다. 이 구현에서는 스패닝 트리가 그래프의 루트부터 시작하는 것을 항상 고려합니다.
보조 공간: 오(V)
Prim 알고리즘의 다른 구현:
아래에는 Prim 알고리즘의 다른 구현이 나와 있습니다.
- 인접 행렬 표현을 위한 Prim의 알고리즘 – 이번 글에서는 그래프가 인접 행렬로 표현되는 경우 프림 알고리즘을 구현하는 방법에 대해 논의했습니다.
- 인접 목록 표현을 위한 Prim의 알고리즘 – 이 기사에서는 인접 목록으로 표시되는 그래프에 대한 Prim의 알고리즘 구현에 대해 설명합니다.
- 우선순위 대기열을 사용하는 Prim의 알고리즘: 이 기사에서는 Prim의 알고리즘을 구현하기 위한 시간 효율적인 접근 방식에 대해 논의했습니다.
PRIM 알고리즘의 최적화된 접근 방식:
직관
- 다음을 사용하여 인접 행렬을 인접 목록으로 변환합니다. 배열목록
. - 그런 다음 꼭지점과 해당 가중치를 저장하기 위해 쌍 클래스를 만듭니다.
- 가장 낮은 가중치를 기준으로 목록을 정렬합니다.
- 우선순위 큐를 생성하고 첫 번째 정점과 그 가중치를 큐에 푸시합니다.
- 그런 다음 가장자리를 순회하고 가장 작은 가중치를 변수에 저장합니다. 연령.
- 마침내 모든 꼭지점 이후에 우리는 ans를 반환합니다.
구현
C++
#include> using> namespace> std;> typedef> pair<>int>,>int>>삐;> // Function to find sum of weights of edges of the Minimum Spanning Tree.> int> spanningTree(>int> V,>int> E,>int> edges[][3])> {> >// Create an adjacency list representation of the graph> >vectorint>> 조정[V]; // 인접 목록을 가장자리와 해당 가중치로 채웁니다. for (int i = 0; i int u = edge[i][0]; int v = edge[i][1]; int wt = edge[i][2 ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}) } // 가중치를 사용하여 에지를 저장하기 위한 우선순위 큐를 생성합니다. 방문한 정점 벡터를 추적하기 위한 방문 배열 |
>
>
자바
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency list> // representation of the graph> import> java.io.*;> import> java.util.*;> // Class to form pair> class> Pair>implements> Comparable> {> >int> v;> >int> wt;> >Pair(>int> v,>int> wt)> >{> >this>.v=v;> >this>.wt=wt;> >}> >public> int> compareTo(Pair that)> >{> >return> this>.wt-that.wt;> >}> }> class> GFG {> // Function of spanning tree> static> int> spanningTree(>int> V,>int> E,>int> edges[][])> >{> >ArrayList adj=>new> ArrayList();> >for>(>int> i=>0>;i { adj.add(new ArrayList()); } for(int i=0;i { int u=edges[i][0]; int v=edges[i][1]; int wt=edges[i][2]; adj.get(u).add(new Pair(v,wt)); adj.get(v).add(new Pair(u,wt)); } PriorityQueue pq = new PriorityQueue(); pq.add(new Pair(0,0)); int[] vis=new int[V]; int s=0; while(!pq.isEmpty()) { Pair node=pq.poll(); int v=node.v; int wt=node.wt; if(vis[v]==1) continue; s+=wt; vis[v]=1; for(Pair it:adj.get(v)) { if(vis[it.v]==0) { pq.add(new Pair(it.v,it.wt)); } } } return s; } // Driver code public static void main (String[] args) { int graph[][] = new int[][] {{0,1,5}, {1,2,3}, {0,2,1}}; // Function call System.out.println(spanningTree(3,3,graph)); } }> |
>
>
파이썬3
import> heapq> def> tree(V, E, edges):> ># Create an adjacency list representation of the graph> >adj>=> [[]>for> _>in> range>(V)]> ># Fill the adjacency list with edges and their weights> >for> i>in> range>(E):> >u, v, wt>=> edges[i]> >adj[u].append((v, wt))> >adj[v].append((u, wt))> ># Create a priority queue to store edges with their weights> >pq>=> []> ># Create a visited array to keep track of visited vertices> >visited>=> [>False>]>*> V> ># Variable to store the result (sum of edge weights)> >res>=> 0> ># Start with vertex 0> >heapq.heappush(pq, (>0>,>0>))> ># Perform Prim's algorithm to find the Minimum Spanning Tree> >while> pq:> >wt, u>=> heapq.heappop(pq)> >if> visited[u]:> >continue> ># Skip if the vertex is already visited> >res>+>=> wt> ># Add the edge weight to the result> >visited[u]>=> True> ># Mark the vertex as visited> ># Explore the adjacent vertices> >for> v, weight>in> adj[u]:> >if> not> visited[v]:> >heapq.heappush(pq, (weight, v))> ># Add the adjacent edge to the priority queue> >return> res> ># Return the sum of edge weights of the Minimum Spanning Tree> if> __name__>=>=> '__main__'>:> >graph>=> [[>0>,>1>,>5>],> >[>1>,>2>,>3>],> >[>0>,>2>,>1>]]> ># Function call> >print>(tree(>3>,>3>, graph))> |
>
>
씨#
using> System;> using> System.Collections.Generic;> public> class> MinimumSpanningTree> {> >// Function to find sum of weights of edges of the Minimum Spanning Tree.> >public> static> int> SpanningTree(>int> V,>int> E,>int>[,] edges)> >{> >// Create an adjacency list representation of the graph> >Listint[]>> 조정 = 새로운 Listint[]>>(); for (int i = 0; i { adj.Add(새 목록 |
>
>
자바스크립트
class PriorityQueue {> >constructor() {> >this>.heap = [];> >}> >enqueue(value) {> >this>.heap.push(value);> >let i =>this>.heap.length - 1;> >while> (i>0) {> >let j = Math.floor((i - 1) / 2);> >if> (>this>.heap[i][0]>=>this>.heap[j][0]) {> >break>;> >}> >[>this>.heap[i],>this>.heap[j]] = [>this>.heap[j],>this>.heap[i]];> >i = j;> >}> >}> >dequeue() {> >if> (>this>.heap.length === 0) {> >throw> new> Error(>'Queue is empty'>);> >}> >let i =>this>.heap.length - 1;> >const result =>this>.heap[0];> >this>.heap[0] =>this>.heap[i];> >this>.heap.pop();> >i--;> >let j = 0;> >while> (>true>) {> >const left = j * 2 + 1;> >if> (left>나) {> >break>;> >}> >const right = left + 1;> >let k = left;> >if> (right <= i &&>this>.heap[right][0] <>this>.heap[left][0]) {> >k = right;> >}> >if> (>this>.heap[j][0] <=>this>.heap[k][0]) {> >break>;> >}> >[>this>.heap[j],>this>.heap[k]] = [>this>.heap[k],>this>.heap[j]];> >j = k;> >}> >return> result;> >}> >get count() {> >return> this>.heap.length;> >}> }> function> spanningTree(V, E, edges) {> >// Create an adjacency list representation of the graph> >const adj =>new> Array(V).fill(>null>).map(() =>[]);> >// Fill the adjacency list with edges and their weights> >for> (let i = 0; i const [u, v, wt] = edges[i]; adj[u].push([v, wt]); adj[v].push([u, wt]); } // Create a priority queue to store edges with their weights const pq = new PriorityQueue(); // Create a visited array to keep track of visited vertices const visited = new Array(V).fill(false); // Variable to store the result (sum of edge weights) let res = 0; // Start with vertex 0 pq.enqueue([0, 0]); // Perform Prim's algorithm to find the Minimum Spanning Tree while (pq.count>0) { const p = pq.dequeue(); const wt = p[0]; // 가장자리의 가중치 const u = p[1]; // 가장자리에 연결된 정점 if (visited[u]) { continue; // 정점을 이미 방문한 경우 건너뛰기 } res += wt; // 방문한 결과에 간선 가중치를 추가합니다.[u] = true; // 정점을 방문한 것으로 표시 // 인접한 정점 탐색 for (const v of adj[u]) { // v[0]은 정점을 나타내고 v[1]은 간선 가중치를 나타냅니다. if (!visited[v[0 ]]) { pq.enqueue([v[1], v[0]]); // 우선순위 큐에 인접한 가장자리를 추가합니다. } } } return res; // 최소 스패닝 트리의 간선 가중치의 합을 반환합니다. } // 사용 예 const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // 함수 호출 console.log(spanningTree(3, 3, graph));> |
>
러드야드 키플링을 한 줄씩 설명한다면
>산출
4>
Prim 알고리즘의 복잡성 분석:
시간 복잡도: O(E*log(E)) 여기서 E는 간선 수입니다.
보조 공간: O(V^2) 여기서 V는 정점 수입니다.
최소 스패닝 트리(MST)를 찾는 Prim의 알고리즘:
장점:
- Prim의 알고리즘은 연결된 가중치 그래프에서 MST를 찾는 것이 보장됩니다.
- 바이너리 힙 또는 피보나치 힙을 사용하면 O(E log V)의 시간 복잡도를 갖습니다. 여기서 E는 모서리 수이고 V는 정점 수입니다.
- 다른 MST 알고리즘에 비해 이해하고 구현하기가 비교적 간단한 알고리즘입니다.
단점:
- Kruskal의 알고리즘과 마찬가지로 Prim의 알고리즘은 모든 가장자리를 한 번 이상 반복해야 하기 때문에 가장자리가 많은 조밀한 그래프에서 속도가 느려질 수 있습니다.
- Prim의 알고리즘은 우선순위 대기열을 사용하므로 매우 큰 그래프에서 추가 메모리를 차지하고 알고리즘 속도가 느려질 수 있습니다.
- 시작 노드 선택은 MST 출력에 영향을 미칠 수 있으며 이는 일부 애플리케이션에서는 바람직하지 않을 수 있습니다.