Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [depth-first-search]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
11 views

Is it correct to say that DepthFirst Search has the space complexity O(bm) and DepthFirst IterativeDeepening O(d)?

Is it correct to state that the space complexity of Depth-First Search (DFS) is O(bm) and that of Depth-First Iterative Deepening (DFID) is O(d)? Here, 'b' represents the branching factor, 'm' the ...
Martin's user avatar
  • 1
-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
1 vote
1 answer
94 views

Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
Nakib's user avatar
  • 11
0 votes
0 answers
16 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
4 votes
2 answers
466 views

How to represent BFS and DFS between adjacency matrix and list?

I'm trying to figure out how to best represent BFS (Breadth First Search) and DFS (Depth First Search) on a graph, specifically between being represented as an adjacency matrix and an adjacency list. ...
MotherHorse's user avatar
2 votes
1 answer
54 views

DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
Michel H's user avatar
  • 123
0 votes
1 answer
95 views

DFS to assign guards to nodes in a tree structure

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum ...
mark's user avatar
  • 67
0 votes
2 answers
63 views

Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue. On the one ...
Root Groves's user avatar
2 votes
2 answers
161 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem: A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
Hugh Mann's user avatar
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
1 vote
2 answers
304 views

Why compute finish time in topological sort

In depth first search each vertex can be associated with a discovery time and a finish time. I am reading the following implementation of topological sort in terms of depth first search ...
shark's user avatar
  • 11
1 vote
1 answer
376 views

Checking if there exists a 'source' vertex

In a directed graph $G=(V,E)$ we denote a vertex $s\in V$ to be a 'source' if there exists in $G$ a path from $s$ to all other vertices $u \in V$. The problem asks for an efficient algorithm to return ...
Aishgadol's user avatar
  • 355
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
-1 votes
1 answer
276 views

Find a Global Sink in a graph

There is a class exercise question asking about global sink in a directed graph. Finding normal sink is not difficult but the conditions of the question have made me stuck on this question. Let $G=(V,...
EmilyI's user avatar
  • 1
2 votes
1 answer
1k views

How to determine the time and memory complexity for solving a sliding-tile puzzle?

I have seen many posts which were related to algorithms for solving an N⨯N puzzle, but I could not figure out the time complexity or memory complexity in these algorithms, especially when we want to ...
Aylin Naebzadeh's user avatar
0 votes
1 answer
190 views

Minimizing/Maximizing recursion depth for DFS

The idea for this problem comes from GATE CS 2014 Set-3 Q13. Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth? Consider the graph from ...
Rinkesh P's user avatar
  • 1,024
1 vote
1 answer
112 views

Recursive DFS Problem

I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf Short summary ...
Stef Man's user avatar
1 vote
1 answer
526 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
2 votes
1 answer
186 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
254 views

Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book

I'm reading the DFS section of CLRS-Introduction to Algorithms, and confuse on the $\Leftarrow$ direction of the proof of the white-path theorem of DFS algorithm in this book. Note that each node u ...
minh quý lê's user avatar
2 votes
3 answers
1k views

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

Given a undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=2022n$ and some weight function $w\colon E\to \mathbb{R}$, and $0≤ w(e) ≤n$ for all $e∈E$, Describe an algorithm that determines if the MST ...
Saar BK's user avatar
  • 55
1 vote
1 answer
78 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 ...
KiwiKiwi's user avatar
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
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
1 answer
667 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 ...
AlessandroF's user avatar
1 vote
1 answer
50 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 ...
nuemlouno's user avatar
0 votes
1 answer
2k 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 ...
Redman's user avatar
  • 25
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
-2 votes
1 answer
8k 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 ...
Saif Haider's user avatar
0 votes
1 answer
513 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 ...
Veera Kumar's user avatar
0 votes
0 answers
171 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 ...
Siddharth VS's user avatar
2 votes
1 answer
139 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 ...
vesii's user avatar
  • 223
1 vote
1 answer
64 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 ...
abuka123's user avatar
  • 115
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
3 answers
2k 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 ...
user5965026's user avatar
1 vote
0 answers
29 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 ...
user941749's user avatar
3 votes
1 answer
1k 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 ...
user avatar
1 vote
1 answer
429 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. ...
Benny 's user avatar
  • 71
0 votes
1 answer
193 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?
Tabris's user avatar
  • 3
2 votes
1 answer
166 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, ...
Mika2019's user avatar
0 votes
1 answer
191 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 ...
heretoinfinity's user avatar
0 votes
0 answers
29 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 ...
Fandi Bataineh's user avatar
1 vote
1 answer
64 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 ...
heretoinfinity's user avatar
0 votes
1 answer
362 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 ...
OuttaSpaceTime's user avatar
2 votes
1 answer
352 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, ...
heretoinfinity's user avatar
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
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
1 answer
260 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 ...
Arat254's user avatar
  • 227
1 vote
1 answer
224 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 ...
PatelisGM's user avatar