Share Your Experience: Take the 2024 Developer Survey

Questions tagged [depth-first-search]

The tag has no usage guidance.

70 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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 ...
• 11
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 ...
• 493
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. ...
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 ...
• 123
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 ...
• 67
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 ...
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$ ...
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. ...
1 vote
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 ...
• 11
1 vote
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 ...
• 355
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 ...