Questions tagged [depth-first-search]
The depth-first-search tag has no usage guidance.
50
questions
1
vote
1answer
31 views
Minimum steps needed to partially cover a sequence of points on a grid
Problem statement: You are in a 2D grid where you can move in any of the 4 directions, no obstacles. You start at position (0, 0).
We say that you partially cover a point $(x,y)$ if your position has ...
0
votes
0answers
31 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 ...
2
votes
0answers
18 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):
...
0
votes
1answer
31 views
What is the relation between Topological Sort and Strongly Connected Components?
Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex.
I find difficult to find an explaination because ...
1
vote
1answer
38 views
Transforming from neighbour representation to grid representation
Assuming I have a list L of lists. Each list in L has four entries [North, Ost, South, West] which represents the neighbours of a point i on a grid. If the entry is 0, the grid neighbour is not ...
0
votes
1answer
77 views
modify dfs to find longest path
Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$.
For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
1
vote
0answers
17 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 ...
0
votes
0answers
42 views
Shortest path with color constraints
Find shortest path in directed graph (blue and red nodes) that never visits 3 red nodes in a row in $O(V+E)$ time.
Not really sure how to approach this.
-3
votes
1answer
1k views
Print all nodes which are the endpoint of the diameter of a tree
Given a tree with n nodes, Print all nodes which are the endpoint of the diameter.
1<= n <=100000.
E.g.
For Above tree answer would be A,B,F,G
I tried the O(n2) approach (Running Dfs from each ...
0
votes
1answer
58 views
Connectivity in Directed Graph
Connectivity in undirected graph can be easily identified using Disjoint Union Set (Union Find). Is there any way to check connectivity in a directed graph efficiently other than doing Depth First ...
0
votes
0answers
28 views
Iterative version of depth-first-search code to detect cycle in a directed graph [duplicate]
I have solved a problem that required me to find if the given directed graph had a cycle or not. The deal is, I used a recursive approach to solve it in the depth-first-search method. I was just ...
1
vote
1answer
51 views
In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest
Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section:
Depth-first search yields valuable ...
1
vote
1answer
56 views
For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees
I suspect that it is not true but I came across with the following statement:
For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross ...
0
votes
1answer
33 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.
...
0
votes
2answers
155 views
Is DFS better than BFS for space complexity when finding path from root to a node in a tree?
For simplicity, and I think without loss of generality, we can consider a binary tree. Suppose that we want to find the path between the root node and some node in the tree (we don't know where it is ...
1
vote
0answers
20 views
Time to form a complete graph from n vertices given that only k vertices can be used at a time [closed]
I know this problem is related to the greedy algorithm and max edges incomplete graph but can't come up with a solution.
Problem
You are given two numbers n and k:
n >= k
n is the total # of ...
3
votes
1answer
453 views
Find palindrome in directed Graph where edges are either blue or red
This is the given task:
Suppose you are given an arbitrary directed graph G in which each edge is
colored either red or blue, along with two special vertices s and t.
Describe an algorithm that either ...
1
vote
1answer
77 views
Check if two graphs are edge-disjoint
Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of
their edge sets is empty.
Assume both $G$ and $H$ are represented by adjacency matrices.
...
0
votes
1answer
66 views
DFS produces the correct Topologically ordered sequence
Prove that DFS produces the correct topologically ordered sequence.
I am having a hard time understanding the question itself. Should I prove the correctness of DFS? Should I use the pseudocode?
0
votes
0answers
33 views
Iterative Deepening DFS for DAGs
Does Iterative Deepening DFS only guarantee the shortest path for DAGs, assuming a visited list is used to prevent infinite cycles?
I can't seem to find any answers online specifically related to ...
2
votes
1answer
23 views
find the strong component containing the vertex v
I'm trying to solve this question for practising purposes:
"Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, ...
0
votes
1answer
70 views
Alternatives for finding sources in a DAG
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:
Property Every dag has at least one source ...
0
votes
0answers
21 views
I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners [duplicate]
I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at ...
1
vote
1answer
29 views
Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?
I came across the chalk-and-string labyrinth analogy for depth-first search in Algorithms by Dasgupta et al. I have seen the code for the depth first search.
Everybody knows that all you need to ...
0
votes
1answer
142 views
Create Shortest Path tree for every node after Floyd Warshall in O(nm)
Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
2
votes
1answer
41 views
pictorial representation of pre and post ordering for edge types
I am reading chapter 3 Decomposition of Graphs of Algorithms by Dasgupta, Papadimitriou & Vazirani and they show a pictorial representation of pre and post numbers with brackets for tree, forward, ...
0
votes
0answers
21 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. ...
1
vote
0answers
36 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
1answer
138 views
Question about the conditions to find articulation points in a graph
I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.
In it, we first ...
1
vote
1answer
55 views
Maximum Independent Set of special Directed Graph
I was given this special type of Directed Graph and was asked to find it's Maximum Independent Set.
Graph Properties :
Graph has $N$ vertices and $N$ edges
There can be no edge from a vertex $v$ to ...
0
votes
1answer
1k views
Why is DFS not suited for shortest path problem?
I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know ...
1
vote
0answers
269 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 ...
1
vote
2answers
626 views
Does DFS have better constants/complexity than Backtracking on a Graph?
I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
4
votes
1answer
113 views
First-time and second-time seen edges in DFS on undirected graphs
Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on ...
0
votes
0answers
146 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
...
1
vote
1answer
173 views
What's the name of this DFS variation
Classical DFS:
A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic.
A DFS ...
5
votes
2answers
180 views
Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value
The question was asked in an interview, and I'm not sure if this is the most optimized answer, but here goes-
You have an undirected acyclic graph, where each node has a non-negative value ...
0
votes
1answer
631 views
Time complexity of DFS and recurrence relation
Is it possible to compute time complexity of Depth First Search (recursive version) which is O(E+V) using a recurrence relation?
0
votes
1answer
74 views
Solving a maze with DFS vs "wall following"
Consider a problem where a "robot cleaner" is placed on a room modeled as a grid. Each cell in the grid can be empty or blocked and all accessible cells are connected, meaning, all empty cells will be ...
6
votes
0answers
87 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,...
0
votes
0answers
102 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 ...
1
vote
0answers
68 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.
...
3
votes
0answers
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
votes
2answers
2k views
Iterative Depth First Search for cycle detection on directed graphs
I found this pseudocode on Wikipedia, and looks very elegant and intuitive:
...
3
votes
2answers
134 views
Articulation points (or cut vertices), but only subset of vertices need to be connected
I know we can find all articulation points efficiently in a graph using DFS.
But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is ...
0
votes
0answers
61 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 ...
5
votes
2answers
789 views
Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?
Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription.
The question:
Given an undirected tree (tree is not disjoint), ...
1
vote
1answer
1k views
Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node
For this I came up with a DFS recursion.
Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.
The element with ...
2
votes
1answer
2k views
What is the correct complexity of All paths from Source to Target DFS solution?
The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."
The DFS solution is described here. https://leetcode.com/...
2
votes
0answers
2k 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,...
