CODEWITHSUNDEEP
c++algorithmgraphtreedepth-first-search
MDS18
MDS18

Reputation: 91

DFS with stack to find length of longest path from a certain node in a directed, acyclic, unweighted graph

I am trying to figure out a way to implement a DFS search to find the length of the longest path from a given node on a directed graph represented as an adjacency list by using a stack, and not using recursion. Specifically, I want to implement the DFS search so that as it runs, the stack gets populated as shown in the picture below..

If that isn't clear, this video is sort of how I want the stack to be built up as my program runs (DFS starts at around 12:45 : https://www.youtube.com/watch?v=pcKY4hjDrxk But im struggling to find a way to achieve this, as I am still pretty new to programming in general. My current code represents the graph as an unordered map, with each entry containing a vector of all the nodes that point to it. i.e:

std::unordered_map<long, std::vector<long>> nodes;

And basically, I want to implement a DFS search from all nodes with a key value of -1 in that unordered_map as shown in the picture and in the video- with the stack getting allocated as shown. I was thinking, that way I can just record when the stack reaches its maximum size, and that would be the longest path.

One thing to note is the graphs in this specific problem is that each edge will only have one outgoing degree, as shown in the picture.enter image description here. Is this possible, or will I have to use some sort of recursion to do what I want? Thanks in advance for any help.

Upvotes: 1

Views: 1661

Answers (2)

shiponcs
shiponcs

Reputation: 1687

Although it's possible to achieve this without recursion, as an alternative, I would suggest you to design a function this way, which requires you to write less code and which will provide the nice intuition to understand this algorithm for you're a beginner. And you'll not need to think about creating stack by your own

const int n = 100;
vector< int > graph[n];
int ans = 0, level = 0;
int vis[n];
void dfs(int src) {
  level++;
  ans = max(level, ans);
  for (int x: graph[src]) {
    if(vis[x]) continue;
    vis[x] = 1;
    dfs(x);
    level--;
  }
}

I hard coded the value of n and graph you can change it as you need as required structure.

Where we take the advantages of the stack created for the recursion tree by the program. This function will work in O(V+E) for a given graph of V nodes and E edges.

Note that, if your Graph is so large that the stack created default by the program can't handle, then you still have to write your own stack to handle the recursion.

Upvotes: 0

comingstorm
comingstorm

Reputation: 26117

You can probably use a task list instead of recursion. If you use the task list in FIFO order like a queue, you get a breadth-first search; if you use it LIFO like a stack, you get depth-first behavior.

However, note that it is possible for a DAG with N nodes to have O(2^(N/2)) possible paths! You should not need to evaluate all possible paths to solve your problem, though, so be careful not to write an algorithm that can take exponential time.

In order to do that, you will need to mark which nodes you have processed. Also, since you are looking for the longest path, you'll need to track per-node information about the longest path found so far.

Upvotes: 1

Related Questions