Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
78
votes
8answers
53k views

Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
25
votes
7answers
39k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
15
votes
4answers
8k views

The purpose of grey node in graph depth-first search

In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (...
14
votes
2answers
2k views

Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
13
votes
1answer
331 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
11
votes
4answers
3k views

Can the pre-order traversal of two different trees be the same even though they are different?

This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal. It is also mentioned that the in-order ...
11
votes
3answers
1k views

What is the meaning of 'breadth' in breadth first search?

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this: Breadth-...
11
votes
2answers
4k views

Number of possible search paths when searching in BST

I have the following question, but don't have answer for this. I would appreciate if my method is correct : Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
11
votes
1answer
2k views

Graphs that cause DFS and BFS to process nodes in the exact same order

For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-...
10
votes
3answers
47k views

Difference between cross edges and forward edges in a DFT

In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal). There are some leftover edges connecting some of the other nodes. What is the difference ...
9
votes
3answers
2k views

Unique path in a directed graph

I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ...
9
votes
2answers
7k views

Why is DFS considered to have $O(bm)$ space complexity?

According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space. The same is ...
9
votes
1answer
5k views

Finding the k-shortest path between two nodes

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-...
8
votes
3answers
926 views

Finding the height of all nodes in a forest

I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges ...
8
votes
2answers
3k views

Correctness of Strongly Connected Components algorithm for a directed graph

I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$....
7
votes
2answers
5k views

What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and ...
7
votes
1answer
20k views

Time complexity of Depth First Search [closed]

Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about. I ...
6
votes
3answers
16k views

Why does DFS only yield tree and back edges on undirected, connected graphs?

Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge. Now, from intuition and in class lectures by Steven Skiena, I know ...
6
votes
1answer
629 views

Logspace algorithm for s-t connectivity in undirected forests

It has been shown that the decision problem $\{(G, s, t)~\mid~ G\text{ is an undirected forest and there is a path from }s \text{ to } t \}$ is complete for logspace (and therefore in $L$). But the ...
6
votes
1answer
4k views

A Good Resource for Christofides' Heuristic

Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound? To be specific: (Disclaimer : I am an engineer who knows ...
6
votes
3answers
123 views

Can two neighbors in a graph be at the same depth in a DFS tree?

In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)
6
votes
1answer
912 views

A variant of travel salesman problem in grid graph

In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. ...
6
votes
2answers
140 views

Traversing a graph with respect to some partial order

Recently I was faced with the following Graph traversal problem: "Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented ...
6
votes
2answers
779 views

Efficiently check if any vertex has a path to its partner vertex

So I have a directed graph that looks something like: I'm trying to make an algorithm that can go through all the vertices and tell me whether we have any path from an upper case letter to its ...
6
votes
1answer
510 views

Backward data-flow: post-order or RPO on reverse CFG?

When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which ...
5
votes
3answers
395 views

Is it possible to reconstruct graph if we have given matrix of shortest pairs

I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally: Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such ...
5
votes
2answers
3k views

How does DFS produce MST and All pairs shortest paths in unweighted graphs?

I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me. For an unweighted graph, DFS traversal of the ...
5
votes
2answers
8k views

Linear-time algorithm to find an odd-length cycle in a directed graph

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related post@cs....
5
votes
1answer
140 views

What is the optimal solution to prove the reachbility of a node from the root?

I have a finite automaton with these properties: Contains cycles It's a directed graph All the states/nodes are initialy reachable from the initial state It has final states but I guess it isn't ...
5
votes
1answer
37 views

Existence of interval arrangement satisfying constraints

Problem statement: Input: (a) A natural number $n$. (b) $m$ requirements on $I_1,\ldots,I_n$ of the form: Segment $I_i$ is entirely to the right of segment $I_j$. Segments $I_i$...
5
votes
1answer
103 views

How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?

"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation ...
5
votes
2answers
1k views

How do I structure hexagon edge data?

In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above. I want to know how many blue tiles ...
5
votes
1answer
61 views

Least number of guesses needed to determine all unknown subsets of a set

Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
5
votes
1answer
427 views

Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space

Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$. I know you can traverse the tree in level order in $\mathcal O(n)$ time using a ...
5
votes
1answer
198 views

Unique path sums in a DAG using vertex instrumentation

I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control ...
5
votes
1answer
371 views

Question about the formal proof of the inorder traversing

In Don Knuth's famous series of books, The Art of Computer Programming, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack: T1 [Initialize....
5
votes
0answers
712 views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
5
votes
1answer
470 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
4
votes
3answers
3k views

Algorithm for getting the outer boundary of a large graph

I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of ...
4
votes
2answers
5k views

What do we do instead of DFS on directed graphs?

All the example of DFS I've seen so far are for undirected graph. In a directed graph the basic DFS algorithm won't work because some vertex will be unreachable. The algorithm I'm talking about : ...
4
votes
1answer
9k views

Can Breadth-First Search be Implemented Recursively without Data Structures?

I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through ...
4
votes
1answer
811 views

Algorithm to determine whether a given graph is a caterpillar tree

I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree. A caterpillar tree is a tree that has a path to which ...
4
votes
1answer
1k views

Breadth-first forest

I was reading CLRS about BFS and DFS, and the algorithms presented therein, which I take to be somewhat standard, constructs a forest in DFS that includes all the nodes, whereas BFS only constructs a ...
4
votes
1answer
1k views

Non-recursive (iterative) DFS with $O(n)$ size stack

I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case. ...
4
votes
2answers
743 views

Why Iterative-Deepening-DFS requires O(b*d) memory?

After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call. However, I could not understand ...
4
votes
1answer
33 views

How to identify named points by coordinates?

The problem: This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (...
4
votes
1answer
128 views

Given an oriented graph, return true if paths have a specified length

I'm having trouble solving this exercise about graphs, I hope you can help me: Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an ...
4
votes
3answers
604 views

Algorithm to Group Vertices of Graph

Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm): ...
4
votes
2answers
92 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
4
votes
1answer
2k views

When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...