最小生成树算法，分别用C语言，C++,java,python编写出来

源码资源网

最小生成树问题，简称MST，指给定一个带权的无向连通图，如果选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树。

图有N个顶点，就一定有N-1条边，且必须包含所有顶点，所有边都在图中。解决最小生成树问题的算法主要有普利姆算法和克鲁斯卡尔算法。

最小生成树算法，分别用C语言，C++,java,python编写出来
当涉及最小生成树算法时，可以使用多种编程语言来实现。以下是使用C语言、C++、Java和Python编写最小生成树算法的示例：
1.**C语言示例：**

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. #include <limits.h>
   
4. #define V 5
   
5. int minKey(int key[], bool mstSet[]) {
   
6.     int min = INT_MAX, min_index;
   
7.      for (int v = 0; v < V; v++) {
   
8.         if (mstSet[v] == false && key[v] < min) {
   
9.             min = key[v];
   
10.             min_index = v;
    
11.         }
    
12.     }
    
13.      return min_index;
    
14. }
    
15. void printMST(int parent[], int graph[V][V]) {
    
16.     printf("Edge \tWeight\n");
    
17.     for (int i = 1; i < V; i++) {
    
18.         printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    
19.     }
    
20. }
    
21. void primMST(int graph[V][V]) {
    
22.     int parent[V];
    
23.     int key[V];
    
24.     bool mstSet[V];
    
25.      for (int i = 0; i < V; i++) {
    
26.         key[i] = INT_MAX;
    
27.         mstSet[i] = false;
    
28.     }
    
29.      key[0] = 0;
    
30.     parent[0] = -1;
    
31.      for (int count = 0; count < V - 1; count++) {
    
32.         int u = minKey(key, mstSet);
    
33.         mstSet[u] = true;
    
34.          for (int v = 0; v < V; v++) {
    
35.             if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
    
36.                 parent[v] = u;
    
37.                 key[v] = graph[u][v];
    
38.             }
    
39.         }
    
40.     }
    
41.      printMST(parent, graph);
    
42. }
    
43. 
    

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

2.**C++示例：**

1. #include <iostream>
   
2. #include <climits>
   
3. using namespace std;
   
4. #define V 5
   
5. int minKey(int key[], bool mstSet[]) {
   
6.     int min = INT_MAX, min_index;
   
7.      for (int v = 0; v < V; v++) {
   
8.         if (mstSet[v] == false && key[v] < min) {
   
9.             min = key[v];
   
10.             min_index = v;
    
11.         }
    
12.     }
    
13.      return min_index;
    
14. }
    
15. void printMST(int parent[], int graph[V][V]) {
    
16.     cout << "Edge \tWeight\n";
    
17.     for (int i = 1; i < V; i++) {
    
18.         cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl;
    
19.     }
    
20. }
    
21. void primMST(int graph[V][V]) {
    
22.     int parent[V];
    
23.     int key[V];
    
24.     bool mstSet[V];
    
25.      for (int i = 0; i < V; i++) {
    
26.         key[i] = INT_MAX;
    
27.         mstSet[i] = false;
    
28.     }
    
29.      key[0] = 0;
    
30.     parent[0] = -1;
    
31.      for (int count = 0; count < V - 1; count++) {
    
32.         int u = minKey(key, mstSet);
    
33.         mstSet[u] = true;
    
34.          for (int v = 0; v < V; v++) {
    
35.             if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
    
36.                 parent[v] = u;
    
37.                 key[v] = graph[u][v];
    
38.             }
    
39.         }
    
40.     }
    
41.      printMST(parent, graph);
    
42. }
    
43. 
    

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

3.**Java示例：**

1. import java.util.Arrays;
   
2. class MST {
   
3.     private static final int V = 5;
   
4.      int minKey(int key[], Boolean mstSet[]) {
   
5.         int min = Integer.MAX_VALUE, min_index = -1;
   
6.          for (int v = 0; v < V; v++) {
   
7.             if (mstSet[v] == false && key[v] < min) {
   
8.                 min = key[v];
   
9.                 min_index = v;
   
10.             }
    
11.         }
    
12.          return min_index;
    
13.     }
    
14.      void printMST(int parent[], int graph[][]) {
    
15.         System.out.println("Edge \tWeight");
    
16.         for (int i = 1; i < V; i++) {
    
17.             System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    
18.         }
    
19.     }
    
20.      void primMST(int graph[][]) {
    
21.         int parent[] = new int[V];
    
22.         int key[] = new int[V];
    
23.         Boolean mstSet[] = new Boolean[V];
    
24.          Arrays.fill(key, Integer.MAX_VALUE);
    
25.         Arrays.fill(mstSet, false);
    
26.          key[0] = 0;
    
27.         parent[0] = -1;
    
28.          for (int count = 0; count < V - 1; count++) {
    
29.             int u = minKey(key, mstSet);
    
30.             mstSet[u] = true;
    
31.              for (int v = 0; v < V; v++) {
    
32.                 if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
    
33.                     parent[v] = u;
    
34.                     key[v] = graph[u][v];
    
35.                 }
    
36.             }
    
37.         }
    
38.          printMST(parent, graph);
    
39.     }
    
40.    
    
41. }

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

4.**Python示例：**

1. class MST:
   
2.     def __init__(self, vertices):
   
3.         self.V = vertices
   
4.         self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
   
5.      def minKey(self, key, mstSet):
   
6.         min = float("inf")
   
7.         min_index = -1
   
8.          for v in range(self.V):
   
9.             if key[v] < min and mstSet[v] == False:
   
10.                 min = key[v]
    
11.                 min_index = v
    
12.          return min_index
    
13.      def printMST(self, parent):
    
14.         print("Edge \tWeight")
    
15.         for i in range(1, self.V):
    
16.             print(parent[i], "-", i, "\t", self.graph[i][parent[i]])
    
17.      def primMST(self):
    
18.         key = [float("inf")] * self.V
    
19.         parent = [None] * self.V
    
20.         mstSet = [False] * self.V
    
21.          key[0] = 0
    
22.         parent[0] = -1
    
23.          for _ in range(self.V - 1):
    
24.             u = self.minKey(key, mstSet)
    
25.             mstSet[u] = True
    
26.              for v in range(self.V):
    
27.                 if (
    
28.                     self.graph[u][v] > 0
    
29.                     and mstSet[v] == False
    
30.                     and key[v] > self.graph[u][v]
    
31.                 ):
    
32.                     key[v] = self.graph[u][v]
    
33.                     parent[v] = u
    
34.          self.printMST(parent)
    
35. 
    

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

这些示例展示了使用不同编程语言实现最小生成树算法。每个示例都使用了类似的思路，通过选择最小权重的边来构建最小生成树。您可以根据需要修改算法和输入图形。请注意，这只是最小生成树算法的简单示例，实际应用中可能会有更复杂的问题和算法。


扫码关注微信公众号，免费查看完整算法内容。