使用普里姆算法生成最小生成树。使用c++

### C++ 实现 Prim 算法构建最小生成树 为了实现 Prim 算法，在C++中通常会采用邻接矩阵表示图结构。下面是一个基于邻接矩阵的Prim算法的具体实现。 #### 初始化阶段 选取任意一个顶点作为起始节点，创建两个辅助数组`lowcost[]`和`closest[]`用于追踪尚未加入到正在生长的最小生成树中的各顶点至其最近已加入顶点的距离以及该最接近的顶点编号。对于选定的第一个顶点来说，它与自身的距离设为0，并将其余所有未处理过的顶点同第一个顶点之间的实际权重填入`lowcost[]`内[^1]。 ```cpp #include <iostream> #include <climits> // For INT_MAX using namespace std; #define V 5 // Number of vertices in the graph // 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[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (!mstSet[v] && key[v] < min) min = key[v], min_index = v; return min_index; } void primMST(int graph[V][V]) { int parent[V]; // Array to store constructed MST int key[V]; // Key values used to pick minimum weight edge in cut bool mstSet[V]; // To represent set of vertices not yet included in MST // Initialize all keys as INFINITE for (int i = 0; i < V; i++) key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. key[0] = 0; // Make key 0 so that this vertex is picked as first vertex parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (int count = 0; count < V - 1; count++) { int u = minKey(key, mstSet); // Pick the minimum key vertex from the set of vertices not yet processed mstSet[u] = true; // Add the picked vertex to the MST Set // 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 < V; 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] && graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v]; } } // Print the constructed MST stored in parent[] cout << "Edge \tWeight\n"; for (int i = 1; i < V; i++) printf("%d - %d \t%d \n", parent[i], i, graph[parent[i]][i]); } ``` 上述代码展示了完整的Prim算法流程，其中包含了初始化过程、迭代更新临近顶点的信息直至找到全部属于最小生成树成员的过程[^3]。