Printing the longest path in an undirected graph

Question

I am using this code https://www.geeksforgeeks.org/longest-path-undirected-tree/ to find the longest path in an undirected graph. The code uses two times BFS search to find the longest path and then it outputs the start and end of the path and the length. How could I save the path in a list and print it? I save the predecessors in an array int predecessors[n], but of course this doesn't give the path. I know somehow I should modify the pred[V] so it stores a list of predecessors but I don't know how to implement it. Any help is appreciated.

// 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 
} 

// method returns farthest node and its distance from node 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); 
}

// method prints longest path of given tree

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; 
}

// Driver code to test above methods

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; 
}

// Result:

Longest path is from 5 to 7 of length 5

Answer 1

V is not a constant so int dis[V]; is invalid. This is C++, not C.

You need to find a way to return pred from bfs(). You can either:

• declare pred in Graph
• locally in longestPathLength() and modify bfs() to accept an additional argument pred
• locally in bfs() and return it together with pair<int, int>: pair<pair<int, int>, PRED_T> or tuple<int, int, PRED_T>

Imo declare pred inside bfs() is best way to do this. Here I use vector<int> for dis and 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;
}