Prim 算法 · Programiz 中文系列教程

# Prim 算法 > 原文： [https://www.programiz.com/dsa/prim-algorithm](https://www.programiz.com/dsa/prim-algorithm) #### 在本教程中，您將學習 Prim 的算法如何工作。此外，您還將在 C，C++ ，Java 和 Python 中找到 Prim 算法的工作示例。 Prim 的算法是[最小生成樹](/dsa/spanning-tree-and-minimum-spanning-tree#minimum-spanning)算法，該算法將圖作為輸入并找到該圖的邊的子集， * 形成包括每個頂點的樹 * 在可以從圖中形成的所有樹中具有最小的權重總和 * * * ## Prim 的算法如何工作它屬于稱為[貪婪算法](/dsa/greedy-algorithm)的一類算法，該算法可以找到局部最優值，以期找到全局最優值。我們從一個頂點開始，并不斷添加權重最低的邊，直到達到目標為止。實現 Prim 算法的步驟如下： 1. 使用隨機選擇的頂點初始化最小生成樹。 2. 找到將樹連接到新頂點的所有邊，找到最小值并將其添加到樹中 3. 繼續重復步驟 2，直到得到最小的生成樹 * * * ## Prim 算法的示例 ![Start with a weighted graph](https://img.kancloud.cn/8c/d9/8cd9eafa7c167ecb3c0021c82ad836da_1460x616.png "Prim's Algorithm Steps") 從加權圖開始 ![Choose a vertex](https://img.kancloud.cn/32/37/32371f8ce1f42a3942546c1274c103c4_1460x344.png "Prim's Algorithm Steps") 選擇一個頂點 ![Choose the shortest edge from this vertex and add it](https://img.kancloud.cn/9a/3b/9a3b01445be7e953dd55fbcc253e2691_1460x480.png "Prim's Algorithm Steps") 從該頂點選擇最短邊并添加 ![Choose the nearest vertex not yet in the solution](https://img.kancloud.cn/d0/b6/d0b6d113b53530e47617eb2ec0f79165_1460x480.png "Prim's Algorithm Steps") 選擇尚未在解決方案中的最近頂點 ![Choose the nearest edge not yet in the solution, if there are multiple choices, choose one at random](https://img.kancloud.cn/c6/5b/c65b630fab6821007e08df855883124f_1460x476.png "Prim's Algorithm Steps") 選擇尚未出現在解決方案中的最近邊，如果有多個選擇，請隨機選擇一個 ![Repeat until you have a spanning tree](https://img.kancloud.cn/9a/23/9a23985401f86fc2fe55d8cbfe9ffec1_1460x612.png "Prim's Algorithm Steps") 重復直到您有一棵生成樹 * * * ## Prim 算法偽代碼 prim 算法的偽代碼顯示了我們如何創建兩組頂點`U`和`V-U`。 `U`包含已訪問的頂點列表，而`V-U`包含尚未訪問的頂點列表。通過連接最小權重邊，將頂點從集合`V-U`移到集合`U`。 ``` T = ?; U = { 1 }; while (U ≠ V) let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U; T = T ∪ {(u, v)} U = U ∪ {v} ``` * * * ## Python，Java 和 C/C++ 示例盡管使用圖形的[鄰接矩陣](/dsa/graph-adjacency-matrix)表示，但是也可以使用[鄰接表](/dsa/graph-adjacency-list)來實現此算法，以提高效率。 ```py # Prim's Algorithm in Python INF = 9999999 # number of vertices in graph V = 5 # create a 2d array of size 5x5 # for adjacency matrix to represent graph G = [[0, 9, 75, 0, 0], [9, 0, 95, 19, 42], [75, 95, 0, 51, 66], [0, 19, 51, 0, 31], [0, 42, 66, 31, 0]] # create a array to track selected vertex # selected will become true otherwise false selected = [0, 0, 0, 0, 0] # set number of edge to 0 no_edge = 0 # the number of egde in minimum spanning tree will be # always less than(V - 1), where V is number of vertices in # graph # choose 0th vertex and make it true selected[0] = True # print for edge and weight print("Edge : Weight\n") while (no_edge < V - 1): # For every vertex in the set S, find the all adjacent vertices #, calculate the distance from the vertex selected at step 1. # if the vertex is already in the set S, discard it otherwise # choose another vertex nearest to selected vertex at step 1. minimum = INF x = 0 y = 0 for i in range(V): if selected[i]: for j in range(V): if ((not selected[j]) and G[i][j]): # not in selected and there is an edge if minimum > G[i][j]: minimum = G[i][j] x = i y = j print(str(x) + "-" + str(y) + ":" + str(G[x][y])) selected[y] = True no_edge += 1 ``` ```java // Prim's Algorithm in Java import java.util.Arrays; class PGraph { public void Prim(int G[][], int V) { int INF = 9999999; int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false boolean[] selected = new boolean[V]; // set selected false initially Arrays.fill(selected, false); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in // graph // choose 0th vertex and make it true selected[0] = true; // print for edge and weight System.out.println("Edge : Weight"); while (no_edge < V - 1) { // For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise // choose another vertex nearest to selected vertex at step 1. int min = INF; int x = 0; // row number int y = 0; // col number for (int i = 0; i < V; i++) { if (selected[i] == true) { for (int j = 0; j < V; j++) { // not in selected and there is an edge if (!selected[j] && G[i][j] != 0) { if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } System.out.println(x + " - " + y + " : " + G[x][y]); selected[y] = true; no_edge++; } } public static void main(String[] args) { PGraph g = new PGraph(); // number of vertices in grapj int V = 5; // create a 2d array of size 5x5 // for adjacency matrix to represent graph int[][] G = { { 0, 9, 75, 0, 0 }, { 9, 0, 95, 19, 42 }, { 75, 95, 0, 51, 66 }, { 0, 19, 51, 0, 31 }, { 0, 42, 66, 31, 0 } }; g.Prim(G, V); } } ``` ```c // Prim's Algorithm in C #include<stdio.h> #include<stdbool.h> #define INF 9999999 // number of vertices in graph #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}}; int main() { int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight printf("Edge : Weight\n"); while (no_edge < V - 1) { //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } printf("%d - %d : %d\n", x, y, G[x][y]); selected[y] = true; no_edge++; } return 0; } ``` ```cpp // Prim's Algorithm in C++ #include <cstring> #include <iostream> using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}}; int main() { int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight cout << "Edge" << " : " << "Weight"; cout << endl; while (no_edge < V - 1) { //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) { if (selected[i]) { for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } } } } cout << x << " - " << y << " : " << G[x][y]; cout << endl; selected[y] = true; no_edge++; } return 0; } ``` * * * ## Prim 與 Kruskal 算法 [Kruskal 算法](/dsa/kruskal-algorithm)是另一種流行的最小生成樹算法，它使用不同的邏輯來查找圖的 MST。 Kruskal 算法不是從頂點開始，而是對所有邊從低權重到高邊進行排序，并不斷添加最低邊，而忽略那些會產生循環的邊。 * * * ## Prim 的算法復雜度 Prim 算法的時間復雜度為`O(E log V)`。 * * * ## Prim 的算法應用 * 鋪設電線電纜 * 在網絡設計中 * 在網絡周期內制定協議