打印无向图中的最长路径

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 
}

//方法returns最远的节点和它到节点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。

您需要找到从 bfs() 到 return pred 的方法。您可以：

在Graph

pred

本地 longestPathLength() 并修改 bfs() 以接受附加参数 pred
本地 bfs() 和 return 它与 pair<int, int> 一起：pair<pair<int, int>, PRED_T> 或 tuple<int, int, PRED_T>

我在 bfs() 中声明 pred 是最好的方法。这里我用 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;
}

打印无向图中的最长路径

Printing the longest path in an undirected graph

c++

graph

breadth-first-search

undirected-graph

longest-path