c++ - 打印无向图中的最长路径

Question

我正在使用此代码 https://www.geeksforgeeks.org/longest-path-undirected-tree/在无向图中找到最长的路径。该代码使用两次 BFS 搜索找到最长路径，然后输出路径的起点和终点以及长度。如何将路径保存在列表中并打印出来？我将前辈保存在数组 int predecessors[n] 中，但这当然不会给出路径。我知道我应该以某种方式修改 pred[V] 以便它存储前任列表，但我不知道如何实现它。感谢您的帮助。

// C++ program to find longest path of the tree 
#include <bits/stdc++.h> 
using namespace std; 
// This class represents a undirected graph using adjacency list 
class Graph { 
    int V;              // No. of vertices 
    list<int> *adj;     // Pointer to an array containing adjacency lists 

public: 
    Graph(int V);              // Constructor 
    void addEdge(int v, int w);// function to add an edge to graph 
    void longestPathLength();  // prints longest path of the tree 
    pair<int, int> bfs(int u); // function returns maximum distant 
                               // node from u with its distance 
}; 
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w);    // Add w to v’s list. 
    adj[w].push_back(v);    // Since the graph is undirected 
} 

//方法返回最远节点及其与节点u的距离

pair<int, int> Graph::bfs(int u) 
{ 
    //  mark all distance with -1 
    int dis[V]; 
    int pred[V];  \\ I added this to store predecessors
    memset(dis, -1, sizeof(dis)); 
    queue<int> q; 
    q.push(u);

    dis[u] = 0;       //  distance of u from u will be 0 
    pred[u] = {u};  // I added this line

    while (!q.empty()) 
    { 
        int t = q.front();       q.pop(); 
        //  loop for all adjacent nodes of node-t 
        for (auto it = adj[t].begin(); it != adj[t].end(); it++) 
        { 
            int v = *it; 
            cout << "adjacent node:" << v << endl;
            // push node into queue only if it is not visited already 
            if (dis[v] == -1) 
            { 
                q.push(v); 
                // make distance of v, one more than distance of t 
                dis[v] = dis[t] + 1; 
                cout << "parent of adjacent node:" << t << endl;
                pred[v] = t // store the predecessor of v
            } 
        } 
    } 
    int maxDis = 0; 
    int nodeIdx; 
    //  get farthest node distance and its index 
    for (int i = 0; i < V; i++) 
    { 
        if (dis[i] > maxDis) 
        { 
            maxDis = dis[i]; 
            nodeIdx = i; 
        } 
    } 
    return make_pair(nodeIdx, maxDis); 
}

//方法打印给定树的最长路径

void Graph::longestPathLength() 
{ 
    pair<int, int> t1, t2; 

    // first bfs to find one end point of longest path
    t1 = bfs(0); 

    //  second bfs to find actual longest path 
    t2 = bfs(t1.first); 

    cout << "Longest path is from " << t1.first << " to "
         << t2.first << " of length " << t2.second; 
}

//测试上述方法的驱动代码

int main() 
{ 
    // Create a graph given in the example 
    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; 
}

//结果:

Longest path is from 5 to 7 of length 5

Answer 1

V不是常数所以 int dis[V];是无效的。这是 C++，不是 C。

你需要想办法返回pred来自 bfs() .您可以:

• 声明pred在 Graph
• 本地 longestPathLength()并修改bfs()接受附加参数 pred
• 本地 bfs()与pair<int, int>一起归还: pair<pair<int, int>, PRED_T>或 tuple<int, int, PRED_T>

我声明pred里面bfs()是做到这一点的最佳方式。这里我用vector<int>对于 dis和 pred .

class Graph {
...
    pair<pair<int, int>, vector<int>> bfs(int u);
};

pair<pair<int, int>, vector<int>> Graph::bfs(int u) 
{ 
    //  mark all distance with -1 
    vector<int> dis(V, -1);

    vector<int> pred(V);

    queue<int> q;
    ...
                dis[v] = dis[t] + 1;
                pred[v] = t; // store the predecessor of v
            }
    ...
    return make_pair(make_pair(nodeIdx, maxDis), pred);
}

void Graph::longestPathLength() 
{ 
    pair<int, int> t1, t2;

    // first bfs to find one end point of longest path
    t1 = bfs(0).first;

    //  second bfs to find actual longest path 
    auto res = bfs(t1.first); // or  pair<pair<int, int>, vector<int>> res
    t2 = res.first; 

    cout << "Longest path is from " << t1.first << " to "
         << t2.first << " of length " << t2.second << endl;

    // Backtrack from t2.first to t1.first
    for (int t = t2.first; t != t1.first; t = res.second[t]) // `res.second` is `pred`
        cout << t << " ";
    cout << t1.first << endl;
}