如何修改无向图最长路径BFS代码以保存并打印路径

Hey Bruce, let's fix this issue so you can get the full longest path nodes instead of just the endpoints and length.

The problem isn't that you need a list of predecessors—since this is a tree (no cycles), each node will only have one unique predecessor during BFS. Your current pred array is actually sufficient; you just aren't using it to trace back the path after the second BFS. Here's how to modify your code to extract the full path:

Step-by-Step Modifications #

1. Add a predecessor storage member to the Graph class so we can access the predecessor data after BFS runs.
2. Update the BFS function to properly initialize and populate the predecessor storage.
3. Trace back the path after the second BFS using the predecessor data to build the full node sequence.

Modified Complete Code #

#include <bits/stdc++.h>
using namespace std;

class Graph {
    int V; // No. of vertices
    list<int> *adj; // Pointer to adjacency lists
    vector<int> pred; // Store predecessors (added as class member)
public:
    Graph(int V);
    void addEdge(int v, int w);
    void longestPathLength();
    pair<int, int> bfs(int u);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
    pred.resize(V); // Initialize predecessor vector size
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
    adj[w].push_back(v);
}

pair<int, int> Graph::bfs(int u) {
    vector<int> dis(V, -1);
    queue<int> q;

    q.push(u);
    dis[u] = 0;
    pred[u] = u; // Mark start node's predecessor as itself

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int v : adj[t]) {
            if (dis[v] == -1) {
                q.push(v);
                dis[v] = dis[t] + 1;
                pred[v] = t; // Set predecessor of current node
            }
        }
    }

    int maxDis = 0;
    int nodeIdx = u;
    for (int i = 0; i < V; i++) {
        if (dis[i] > maxDis) {
            maxDis = dis[i];
            nodeIdx = i;
        }
    }
    return {nodeIdx, maxDis};
}

void Graph::longestPathLength() {
    pair<int, int> t1 = bfs(0);
    pair<int, int> t2 = bfs(t1.first);

    // Build the full path by tracing back from end to start
    vector<int> path;
    int current = t2.first;
    while (current != t1.first) {
        path.push_back(current);
        current = pred[current];
    }
    path.push_back(t1.first);
    reverse(path.begin(), path.end()); // Reverse to get start-to-end order

    // Output results
    cout << "Longest path is from " << t1.first << " to " << t2.first << " of length " << t2.second << endl;
    cout << "Full path: ";
    for (size_t i = 0; i < path.size(); i++) {
        if (i > 0) cout << " -> ";
        cout << path[i];
    }
    cout << endl;
}

int main() {
    Graph g(10);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(2, 9);
    g.addEdge(2, 4);
    g.addEdge(4, 5);
    g.addEdge(1, 6);
    g.addEdge(6, 7);
    g.addEdge(6, 8);
    g.longestPathLength();
    return 0;
}

What Changed & Why #

• We replaced raw C-style arrays with vector<int> for better safety and standard compliance (variable-length arrays aren't part of standard C++).
• The pred vector is now a class member, so we can access it after the second BFS to trace the path.
• After finding the two endpoints of the longest path, we start from the second endpoint and follow the predecessor links back to the first endpoint. Reversing this collected sequence gives us the path from start to end.

Sample Output #

Longest path is from 5 to 7 of length 5
Full path: 5 -> 4 -> 2 -> 1 -> 6 -> 7

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