# Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

284 questions
Filter by
Sorted by
Tagged with
2answers
102 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 ...
2answers
56 views

### Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in $O(n^2)$: We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
1answer
59 views

### Directed graph where DFS returns on a node before all its child nodes are visited?

Give an example of a directed graph in which a depth-ﬁrst search backs up from a vertex $v$ before all the vertices that can be reached from $v$ via one or more edges are discovered. My professor ...
3answers
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. ...
0answers
15 views

### Why is BFS “vertex based” and DFS “edge based”?

I am trying to understand the various differences between Breadth-first and Depth-first search on graphs. Two sources state that BFS is "vertex based" and DFS is "edge based" even though in ...
0answers
42 views

### Verifying the minimum cost from each node to a sink node in linear time

Problem Statement: Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for ...
1answer
22 views

### how to prove correctness of this BFS algorithm?

Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that ...
0answers
15 views

### Two algorithms for finding bridges in a graph that are almost the same

So I'm looking at an algorithm for finding bridges in an undirected graph. The thing is, there is a version of this algorithm that I've used so far that looks like this (C++) ...
1answer
115 views

### Post numbers in DFS tree of an undirected graph

How could you prove: An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the ...
1answer
744 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, ...
0answers
19 views

### Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
0answers
15 views

### What is the approximation for odd cycle transversal?

What is the best approximation for odd cycle transversal? (on general graphs) Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels
2answers
80 views

### For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1answer
347 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 ...
1answer
225 views

### How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
1answer
293 views

### Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
1answer
99 views

### Printing all paths of a tree and sorting the weight of edges

Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time. To solve this ...
0answers
40 views

### Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
1answer
46 views

### How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with. For example: tree 1 ( (a, b), (c, d) ) Imagine that each tree split represents the function "add", then ...
2answers
153 views

### Solving a in/equality constraint problem with graph search

You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types. An equality constraint of the form xi = xj for some i!=j. An ...
1answer
47 views

### is it always true that the depth of BFS is $\leq$ DFS?

I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS? From what I understand, the tricky part here is the ...
1answer
77 views

### Define the time complexity of Kruskal's algorithm as function

I am trying to define the time complexity of Kruskal's algorithm as function dependant on: the number of vertices V the number of edges ...
2answers
403 views

### is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition): A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at ...
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 ...
0answers
1k views

### Shortest Path using DFS on weighted graphs

I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:- Here if we follow ...
1answer
26 views

### Minimize sequence storage by overlapping prefixes

I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can ...
1answer
64 views

### Cannibals missionaries problem - solving usings graphs

I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other ...
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-...
2answers
67 views

### Minimize number of DFS searches in a graph

I got a weird homework question about graph. A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed ...
0answers
83 views

### Maximum size of BFS open set on a grid

I have a 2D grid of infinite size that can either be 4-connected or 8-connected (as defined in https://en.wikipedia.org/wiki/Pixel_connectivity). I am implementing breadth-first search on this grid ...
1answer
96 views

### Subtree with minimum sum of nodes' costs

Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that ...
2answers
249 views

### Minimum Distance Spanning Tree Dijkstra

I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below: MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)} Is my ...
0answers
27 views

### Are these algorithms for detecting cycles in directional graph correct?

I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not ...
1answer
34 views

### Is a subgraph of G always connected

I am trying to figure out if given a connect graph with N nodes and A edges, its subgraphs are connected. In order word: given a graph G, can I have a subgraph of G that is not connected? Or: can a ...
2answers
196 views

### Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG)

Let G = (V, E) be a graph which is hierarchical in the sense that its vertices are arranged in levels/layers (say 1 to k) and an edge can only be from a vertex at level i to a vertex at level i+1. ...
1answer
38 views

### Idea for a Graph Based Algorithm

Assume there is a Shopping Mall x and all the roads in the city are one way such that, irrespective of the path you take starting from x, you will always end up at vertex x. Device an algorithm to ...
2answers
74 views

### Fewest traversals to visit all vertices of DAG

I want to find the fewest traversals to visit all vertices of a DAG. To take a very simple case: ...
0answers
47 views

### Whats the time complexity of Prims Algo. without heaps (using priority queue)?

Here's my attempt: Initialisation - ...
0answers
31 views

### Implementation of multiple sink shortest pair of disjoint paths problem for multigraphs

I would like to implement the shortest pairs of edge-disjoint paths of Suurballe and Tarjan for multigraphs in the interpretation of Banerjee et al. (http://web.cs.iastate.edu/~pavan/papers/short.pdf, ...
7answers
40k 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 ...
1answer
54 views