编写c++程序，利用普里姆（Prim）算法求最小生成树

好的,我很乐意为您介绍如何使用C++实现普里姆(Prim)算法来求解最小生成树。以下是一个示例程序: ```cpp #include <iostream> #include <vector> #include <climits> using namespace std; const int V = 5; // 图中顶点的数量 // 在尚未包含在最小生成树中的顶点集合中,找到距离最小的顶点 int minKey(int key[], bool mstSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) min = key[v], min_index = v; return min_index; } // 打印构造的最小生成树 void printMST(int parent[], int graph[V][V]) { cout << "Edge \tWeight\n"; for (int i = 1; i < V; i++) cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n"; } // 使用Prim算法构建最小生成树 void primMST(int graph[V][V]) { int parent[V]; // 存储最小生成树的构造 int key[V]; // 用于选择最小权重边 bool mstSet[V]; // 标记顶点是否包含在最小生成树中 // 初始化所有键为无限大 for (int i = 0; i < V; i++) key[i] = INT_MAX, mstSet[i] = false; // 总是包含第一个顶点 key[0] = 0; // 使它成为第一个被选择的顶点 parent[0] = -1; // 根节点 // 构建最小生成树 for (int count = 0; count < V - 1; count++) { // 选择尚未包含在MST中的顶点,其键值最小 int u = minKey(key, mstSet); // 将选择的顶点添加到MST集合中 mstSet[u] = true; // 更新与u相邻顶点的键值 for (int v = 0; v < V; v++) if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v]; } // 打印构造的最小生成树 printMST(parent, graph); } int main() { /* 创建如下图的示例 2 3 (0)--(1)--(2) | / \ | 6| 8/ \5 |7 | / \ | (3)-------(4) 9 */ 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} }; // 打印最小生成树 primMST(graph); return 0; } ``` 这个程序实现了Prim算法来解决最小生成树问题。以下是程序的主要步骤： 1. 我们定义了一个常量V来表示图中顶点的数量。 2. `minKey`函数用于在尚未包含在最小生成树中的顶点集合中,找到键值最小的顶点。 3. `printMST`函数用于打印构造的最小生成树。 4. `primMST`函数实现了Prim算法的主体逻辑： - 初始化所有键值为无限大。 - 将第一个顶点的键值设为0。 - 重复以下步骤V-1次： - 选择键值最小的顶点。 - 将该顶点包含到最小生成树中。 - 更新与该顶点相邻的顶点的键值。 5. 在`main`函数中，我们创建了一个示例图并调用`primMST`函数来求解最小生成树。 这个程序将输出最小生成树的边和相应的权重。