Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [depth-first-search]

The tag has no usage guidance.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
330 views

### When would Kosaraju's algorithm be a better choice than Tarjan's for strongly connected components?

I know both have runtime complexity $\mathcal{O} (V+E)$, but Tarjan's algorithm does a single DFS pass, whereas Kosaraju's does two DFS passes. Both need extra space (e.g. a dynamic set, often a stack,...
1k views

### Backtracking vs Branch-and-Bound

I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound. What confuses me: Stack Overflow: Difference between '...
• 2,360
92 views

### How to mathematically prove that a topological ordering on a cyclic graph will topologically sort its Strongly Connected Components?

Let's have a standard topological ordering algorithm (from CLRS): ...
• 232
5k views

### Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality,...
• 401
184 views

### Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
• 21
1 vote
525 views

### What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...
1 vote
206 views

### Visiting vertices on a graph using DFS and BFS

I have this graph that I created and am wondering how DFS and BFS would work on something like this. I made this graph undirected and am going off the premise that if possible, a vertex should be ...
• 21
1 vote
56 views

### What does "yields" mean in the phrase *yields no back edges* in DFS?

What does yields mean in the phrase yields no back edges in the context of DFS? ...
1 vote
623 views

### Kruskal naive implementation: how to use DFS to detect cycle in MST plus next edge?

Most discussion of naive (without Union-Find) implementations of Kruskal's algorithm for finding the minimal spanning tree that I see has a handwavy bit: "just use DFS to detect if there is a ...
• 111
1 vote
161 views

### Why does this BFS solution work for this question about euclidean distance and what's its complexity?

Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector. ...
• 151
15 views

### How to get the iterator of the ancestor nodes during DFS or BFS?

I am able to solve this by myself, but somebody may already know the answer, so saving manpower, instead of me probably trying several variants. What is an easy way during either DFS or BFS of a DAG ...
• 493
21 views

### Meaning of Depth First Search on certain edges?

I understand depth first search on a graph, but I'm having difficulty understanding what it means to do depth first search on only certain edges. If given an undirected graph, with 2 types of edges, ...
35 views

### Are pre-order, in-order and post-order the only traversals for depth-first search?

With a binary tree, the 3 approaches for the tree below are listed. ...
430 views

### Assigning directions to edges in an undirected graph in a way which satifies some condition

I got the following question from my academic instructor and since I am new to graph algorithms I would be happy if someone could review my solution. Given undirected graph $G = (V,E)$, suggest an ...
• 275
71 views

### I do not understand a way of proving the correctness of the algorithm to compute the Strongly Connected Components

"Introduction to algorithms" also known as CLRS, proves the correctness of the algorithm to compute the Strongly Connected Components in two ways, one of which is Here is another way to ...
• 232
75 views

### Trace minimum spanning tree's path

I have a list of connected rooms, I need to visit each room in the list, but I have to record the exact path to traverse the entire graph. ...
• 121
62 views

### Finding time complexity of a depth first traversal algorithm with a depth limit to get all node traversals starting from the root node

What would be the time complexity of a depth-first traversal algorithm on a graph, that is simply trying to retrieve all nodes being visited from starting node up until a depth limit is reached (i.e. ...
• 13
267 views

### Find every path that passes through certain edges

I'm faced with the following problem: Given Directed and unweighted graph, where each edge E has two attributes Goal Find every path through the 3 (or more) given edges in a specific order ...
179 views

### Exit Condition for Knight's Tour Using Depth-First Search

Suppose I'm using the algorithm below to perform Depth-First Search in a 2d Grid. It seems like it should be possible to adjust it to perform a Knight's Tour with little change. For example I would ...