In the recursive DFS, we can detect a cycle by coloring the nodes as WHITE, GRAY and BLACK as explained here. A cycle exists if a GRAY node is encountered during the DFS search. My question is: W...

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been visited while traversing the tree/graph.

Suppose we have a graph such as: If you wanted a path from 0 to 5, in what order will we visit the nodes if we perform DFS and BFS on this graph (assume the lowest element is always pushed...

I always mix up whether I use a stack or a queue for DFS or BFS. Can someone please provide some intuition about how to remember which algorithm uses which data structure?

Can you please let me know what is incorrect in below DFS code. It's giving correct result AFAIK, but I don't know when it will fail. graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F'...

It seems to me like Pre-order traversal and DFS are same as in both the cases we traverse till the leaf node in a depth wise fashion. Could anyone please correct me if I am wrong? Thanks in advanc...

I want to count total number of directed cycles available in a directed graph (Only count is required). You can assume graph is given as adjacency matrix. I know DFS but could not make a workin...

I understand BFS, and DFS, but for the life of me cannot figure out the difference between iterative deepening and BFS. Apparently Iterative deepening has the same memory usage as DFS, but I am una...

Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS. I have included the problem statement here for ...

I know we can use DFS for maze exploration. But I think we can also use BFS for maze exploration. I'm little bit confused here because most of the books and articles that I've read had used DFS for...

I understand and can easily implement BFS. My question is, how can we make this BFS limited to a certain depth? Suppose, I just need to go 10 level deep.

I know BFS alone can find the shortest path in an unweighted graph but I also read on a couple of sites where people were claiming that either BFS or DFS could do this. I just wanted to confirm tha...

In a bidirectional graph check if a path exists between node A and node B. My code does not work for certain input (samples provided below). Is this implementation correct or I missed something? bo...

I know the common way to do a topological sort is using DFS with recursion. But how would you do it using stack<int> instead of recursion? I need to obtain the reversed post-order but I'm kin...

To make things easier, the table contains all the words in the English dictionary. What I would like to do is be able to store the data as a trie. This way I can traverse the different branches o...

So I know how to create a kernel and to iterate over the processes linearly by simply including linux/sched.h and using the following code: struct task_struct *task; for_each_process(task) { prin...

Extracted from here we got a minimal iterative dfs routine, i call it minimal because you can hardly simplify the code further: def iterative_dfs(graph, start, path=[]): q = [start] while q: v ...

I have read about DFS and BFS many times but I have this doubt lingering my mind since long. In a lot of articles it is mentioned that DFS can get stuck in infinite loops. As far as I know, this l...

I'm having a hard time understanding Tarjan's algorithm for articulation points. I'm currently following this tutorial here: https://www.hackerearth.com/practice/algorithms/graphs/articulation-poin...

The following is pseudocode implement depth-first search(DFS) with one stack and a large table to mark visited nodes: DFS(N0): StackInit(S) S.push((N0, null)) if isGoal(N0) then do return true ...

I am trying to find (using Python) all possible solutions to a maze. I have a DFS script that returns one solution. I am trying to adapt it but I'm really having a hard time wrapping my head around...

I was trying to write code for detecting a cycle in a directed graph and if there is no cycle then return a topological order of the same. While I was searching for it I came across different tec...

According to Norvig in AIMA (Artificial Intelligence: A modern approach), the Depth-first algorithm is not complete (will not always produce a solution) because there are cases when the subtree bei...

What's the difference between a Spanning Tree and a Spanning Forest in graphs, conceptually. Also, is it possible to construct a Spanning Forest through DFS or BFS traversals? Why? How? I underst...

I have written a recursive DFS algorithm to traverse a graph: void Graph<E, N>::DFS(Node n) { std::cout << ReadNode(n) << " "; MarkVisited(n); NodeList adjnodes = Adjacent(n...