修改Prim算法以显示边及最大边权和遇问题求助

Hey there! Let's figure out why your modified Prim's algorithm isn't working. From the snippet you shared, it looks like you're trying to adjust it to output both the sum of the maximum edge weights for a Maximum Spanning Tree (Max MST) and the specific edges in that tree—but there are a few syntax gaps and logical tweaks missing. Let's fix this up step by step.

First, Let's Spot the Obvious Issues in Your Code Snippet #

• You have a typo: vecto... should be vector
• There's no structure to store the edges you select for the MST
• For a Max MST, your priority queue needs to be a max-heap (C++'s default priority queue is a min-heap, which is for standard minimum spanning trees)
• The marked array wasn't properly initialized to avoid invalid node access

Corrected Complete Code #

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#include <algorithm>
using namespace std;

const int MAX = 1e4 + 5;
typedef pair<long long, int> PII;
// Custom type to store MST edges: (start node, end node) + edge weight
typedef pair<pair<int, int>, long long> MSTEdge;

bool marked[MAX];
vector<pair<int, long long>> adj[MAX]; // Adjacency list: adj[u] = list of (connected node, edge weight)
vector<MSTEdge> mst_edges; // Stores all edges in our final Max MST

long long prim_max_mst(int start, int total_nodes) {
    // Create a max-heap (reverse default min-heap behavior with less<PII>)
    priority_queue<PII, vector<PII>, less<PII>> pq;
    long long max_total_weight = 0;
    vector<int> parent(total_nodes + 1, -1); // Track parent node to reconstruct edges
    
    // Initialize all nodes as unvisited
    fill(marked, marked + MAX, false);
    
    pq.push({0, start});
    parent[start] = -1;
    
    while (!pq.empty()) {
        auto [current_weight, u] = pq.top();
        pq.pop();
        
        // Skip if we've already processed this node
        if (marked[u]) continue;
        marked[u] = true;
        
        // Add the edge to MST (skip the dummy 0-weight starting edge)
        if (parent[u] != -1) {
            mst_edges.push_back({{parent[u], u}, current_weight});
            max_total_weight += current_weight;
        }
        
        // Explore all neighbors of current node
        for (auto [v, edge_weight] : adj[u]) {
            if (!marked[v]) {
                pq.push({edge_weight, v});
                parent[v] = u;
            }
        }
    }
    
    return max_total_weight;
}

int main() {
    int node_count, edge_count;
    cout << "Enter number of nodes and edges: ";
    cin >> node_count >> edge_count;
    
    // Build the adjacency list from input
    for (int i = 0; i < edge_count; i++) {
        int u, v;
        long long weight;
        cin >> u >> v >> weight;
        adj[u].push_back({v, weight});
        adj[v].push_back({u, weight});
    }
    
    // Run the modified Prim's algorithm
    long long max_sum = prim_max_mst(1, node_count);
    
    // Output results
    cout << "\nMaximum edge weight sum of the MST: " << max_sum << endl;
    cout << "Edges in the Maximum Spanning Tree:\n";
    for (auto& edge : mst_edges) {
        cout << edge.first.first << " -> " << edge.first.second 
             << " (Weight: " << edge.second << ")\n";
    }
    
    return 0;
}

Key Fixes & Explanations #

• Max-Heap Implementation: We used less<PII> to turn the default min-heap into a max-heap, which is critical for selecting the heaviest valid edges first (required for a Max MST).
• Edge Tracking: Added a parent array to record which node each node was reached from—this lets us reconstruct the exact edges in the MST after the algorithm runs.
• Proper Initialization: Used fill() to ensure all nodes start as unmarked, preventing invalid state access during traversal.
• Structured Edge Storage: Created a custom MSTEdge type to store each edge's start, end, and weight, making it easy to output clear, readable edge details.

How to Test #

1. When prompted, enter the number of nodes and edges in your graph.
2. For each edge, input the two connected nodes and the edge's weight.
3. The program will output the total sum of the Max MST's edge weights, followed by each edge in the tree with its weight.

内容的提问来源于stack exchange，提问作者David Edgar