Skip to main content
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
7 votes
0 answers
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,...
Amelio Vazquez-Reina's user avatar
3 votes
0 answers
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 '...
Martin Thoma's user avatar
  • 2,360
2 votes
0 answers
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): ...
AlessandroF's user avatar
2 votes
0 answers
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,...
mariaprsk's user avatar
  • 401
2 votes
1 answer
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. ...
user1234's user avatar
1 vote
1 answer
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 ...
Toothpick Anemone's user avatar
1 vote
0 answers
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 ...
JJbigs's user avatar
  • 21
1 vote
0 answers
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? ...
Alex Nguyen's user avatar
1 vote
0 answers
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 ...
user125691's user avatar
1 vote
0 answers
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. ...
Joe Black's user avatar
  • 151
0 votes
0 answers
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 ...
porton's user avatar
  • 493
0 votes
0 answers
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, ...
underdog987's user avatar
0 votes
0 answers
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. ...
heretoinfinity's user avatar
0 votes
0 answers
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 ...
Yarin's user avatar
  • 275
0 votes
0 answers
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 ...
AlessandroF's user avatar
0 votes
1 answer
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. ...
Shane's user avatar
  • 121
0 votes
0 answers
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. ...
Ashera's user avatar
  • 13
0 votes
0 answers
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 ...
Thomas Pellegrini's user avatar
0 votes
0 answers
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 ...
Robin Andrews's user avatar
0 votes
0 answers
65 views

Graphs which favour BFS over DFS and vice versa

I am trying to figure out what kinds of graphs are better suited to BFS and which are better suited to DFS. However i'm struggling to visualise what kind of graphs favour which search. Could someone ...
RishtarCode47's user avatar
-1 votes
0 answers
16 views

Using Binary Search to Calculate the nearest 2d Co-ordinate from a list , Leetcode#2812

I am solving this question Problem Link through a different method , the only difference between the the official solution and my approach is that, The official Solution uses BFS(Multisource) to ...
Shubham Kumar's user avatar