Click here to Skip to main content
15,503,491 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
I have this question for ADS passionates. There is a procedure graph. Let's imagine like this. Below I described a graph using an adj list.

adjList = {

A: [B, D],
B: [C],
C: [],
D: [E]
E: [F]
F: []
}

How can you find and count the longest path?
Edge cases:
1. If you find a cycle in the graph return "cycle found", otherwise return the count of the longest path.
2. There may be a case some of the nodes may not be connected. i.e A->B->C D->E. Here D->E nodes are separate from the rest of the nodes.

What I have tried:

I tried to solve the problem. But in my case, I couldn't return the count but I put them into an array. Still, it is not solving the problem, I ended up collecting all the paths into an array.

I used DFS. But I heard that if I use DFS and DP with graph I can solve the problem. Can help me out with this problem?

Javascript, C++, and Java even Python codes are welcome!
Posted
Updated 18-Jan-22 8:05am
Comments
Stefan_Lang 11-Jan-22 5:23am    
Do not assume that anyone reading your question is familiar with the specific methods you happened to have come across, or familiar with the specific names of these methods that you know, even if they do know the method as such. Methods and algorithms tend to be known by different names depending on your source. And not every source introduces abbreviations for such names at all. Therefore abbreviations such as DFS or DP are not helpful!

At the very least provide names that are concise enough to be googled, so the reader will be able to look up if it happens to be something he is familiar with under a different name.

Quote:
Javascript, C++, and Java even Python codes are welcome!
Sorry, this site does not provide code to order. This is your assignment so you are expected to do the work. People here will help with your code if you have specific problems, but no one is going to do your work for you.
 
Share this answer
 
Comments
sharopcha 11-Jan-22 4:55am    
Actually, I don't want a code. I have a code written already. If you've paid attention to my request I've asked how to improve it with DP. Need help with some logic.
Stefan_Lang 11-Jan-22 5:17am    
1. Given how many abbreviations exist in various contexts, you would do well to actually use full names. I have no idea what you are talking about.
2. This may not be the right place to ask, unless you have a concrete issue where you don't know how to implement something with C++ or another programming language - QA is not meant to provide you with the 'something' part, because that would not qualify for the 'Q' (quick) in 'QA'
Richard MacCutchan 11-Jan-22 6:21am    
As I mentioned above, this site is for specific problems. We have no idea what your code is doing, or supposed to do, or what problems need correcting. Without that information there is very little that anyone can suggest.
It is very unlikely that anyone will write this code for you.

I assume that DFS = depth-first search. That will work, but you have to do a DFS starting from each node in the graph. During the search, you'll need to pass a vector of the nodes reached so far, so that you can check if the next node to be added to a path has already been reached (which indicates a cycle).

I don't know what you mean by DP, however.
 
Share this answer
 
Hello,
That's my solution:

1) Use Tarjan's strongly connected components algorithm to find all connected components,

2) If there is any component larger then 1, you have cycle, so your algorithm should return cycle found,

3) If there isn't, you end up with DAG (Directed Acyclic Graph), so you can find topological order (note: if you correctly implement Tarjan's algorithm you also found needed order), for example using DFS algorithm

4) Then go through your DAG after toposorting, and make use of some Dynamic Programming on DAG (this is which DP stands for). So in each vertex store length of the longest path ending in this vertex. To calculate that length use simple formula iterating through each u: len[v] = max(len[v], len[u] + 1) where u is v's father.

5) Then the greatest len[i] (for any i) is your result!

And this is my c++ code for your problem:
C++
const int N = 1e9; // MAX vertices count
vector<int> digraph[N], transpose[N], postorder; // adjacency lists DS
bool visited[N]; // array for counting visited nodes
int n, m, len[N]; // number of vertices and edges

void DFS(int v) {
    visited[v] = true;
    for (int u : digraph[v])
        if (visited[u] == false)
            DFS(u);
    
    postorder.push_back(v);
}

void DFS_2(int v) {
    visited[v] = true;
    for (int u : transpose[v])
        if (visited[u] == false)
            DFS_2(u);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        digraph[u].push_back(v);
        transpose[v].push_back(u);
    }

    for (int v = 1; v <= n; v++)
        if (visited[v] == false)
            DFS(v); // calculating post order, first step of Tarjan's alg
    
    reverse(postorder.begin(), postorder.end());

    for (int v = 1; v <= n; v++)
        visited[v] = false;

    int c = 0; // c is number of strongly connected components
    for (int v : postorder)
        if (visited[v] == false)
            c++, DFS_2(v);

    if (c < n) cout << "cycle found";
    
    int longest = 0; // variable for result 
    for (int v : postorder)
        for (int u : transpose[v])
            len[v] = max(len[v], len[u] + 1);
        longest = max(longest, len[v]);

    cout << "the longest path in graph: " << longest;
}

In terms of time complexity we've got O(n+m) (n is number of nodes and m is number of edges).
 
Share this answer
 
v3

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900