Prim 算法求解带权无向连通图最小生成树边权和：附 C++ 代码及注意点

以下是使用 Prim 算法解决此问题的 C++代码： ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; const int MAXN = 10005; // 最大节点数 const int INF = 1e9; // 无穷大 int n, m; // 节点数和边数 vector<pair<int, int>> graph[MAXN]; // 邻接表存储图 bool visited[MAXN]; // 标记节点是否已访问 int prim() { int res = 0; // 结果 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 最小堆 pq.push({0, 1}); // 从第一个节点开始 while (!pq.empty()) { auto cur = pq.top(); // 取出当前最小边 pq.pop(); int cost = cur.first; // 边权 int node = cur.second; // 节点 if (visited[node]) continue; // 如果已访问过，跳过 visited[node] = true; // 标记已访问 res += cost; // 累加边权 for (auto edge : graph[node]) { // 遍历相邻节点 if (!visited[edge.first]) { // 如果未访问 pq.push({edge.second, edge.first}); // 加入堆 } } } return res; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } cout << prim() << endl; return 0; } ``` 额外需要注意的逻辑点： 1. 邻接表的构建要确保准确，不要遗漏边。 2. 最小堆的操作要注意优先级的设置。 3. 标记已访问节点时要确保正确，避免重复计算。 ######[AI写代码神器 | 504点数解答 | 2024-12-15 15:49:02]