# Questions tagged [depth-first-search]

The tag has no usage guidance.

64 questions
Filter by
Sorted by
Tagged with
41 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 ...
112 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$ ...
20 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, ...
33 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. ...
16 views

### least collection of node disjoint paths that cover a given set of vertices

Given a directed graph G (with cycles) with source and target, and a set of interested vertices S. we want to find a small n collections of vertice-disjoint-paths (path only have common nodes in ...
197 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 ...
1 vote
185 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 ...
335 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 ...
105 views

3k 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
543 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
1k 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 ...
175 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 ...