首页能否提供一个使用C语言或C++编程语言，基于邻接矩阵表示的Prim算法来计算最小生成树的具体实现代码示例？

能否提供一个使用C语言或C++编程语言，基于邻接矩阵表示的Prim算法来计算最小生成树的具体实现代码示例？

时间: 2025-06-16 18:54:17 浏览: 12

当然可以。Prim算法是一种用于寻找无向图中最小生成树的贪心算法。以下是使用C++基于邻接矩阵表示的Prim算法的一个简化版实现： ```cpp #include <iostream> #include <vector> #include <climits> // 定义邻接矩阵 using Graph = std::vector<std::vector<int>>; // 边的结构体 struct Edge { int src, dest, weight; }; int prim(Graph& graph, int n) { bool visited[n + 1] = {false}; int min_cost = 0; std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq; // 小顶堆 for (int i = 0; i <= n; i++) { if (!visited[i]) { visited[i] = true; pq.push({i, INT_MAX, INT_MAX}); } } while (!pq.empty()) { Edge current_edge = pq.top(); pq.pop(); if (current_edge.weight != INT_MAX) { if (!visited[current_edge.dest]) { visited[current_edge.dest] = true; min_cost += current_edge.weight; } for (int neighbor : graph[current_edge.src]) { if (!visited[neighbor] && graph[current_edge.src][neighbor] < current_edge.weight) { pq.push({neighbor, graph[current_edge.src][neighbor], min_cost}); } } } } return min_cost; } int main() { int n; // 顶点数 std::cout << "Enter number of vertices: "; std::cin >> n; Graph graph(n); // 填充邻接矩阵... // 示例：graph[i][j] 存储从节点i到节点j的边的权重 int result = prim(graph, n); std::cout << "Minimum spanning tree cost is: " << result << std::endl; return 0; } ```

阅读全文