Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
278
questions
2
votes
2answers
58 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 ...
0
votes
1answer
35 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 ...
2
votes
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 ...
2
votes
1answer
46 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 ...
2
votes
1answer
42 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 ...
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 ...
2
votes
1answer
24 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 ...
3
votes
1answer
55 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 ...
3
votes
2answers
63 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 ...
1
vote
0answers
75 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 ...
2
votes
1answer
92 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 ...
1
vote
1answer
74 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 ...
0
votes
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 ...
0
votes
1answer
32 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 ...
0
votes
1answer
37 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 ...
3
votes
2answers
73 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:
...
0
votes
0answers
42 views
Whats the time complexity of Prims Algo. without heaps (using priority queue)?
Here's my attempt:
Initialisation -
...
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-...
2
votes
1answer
52 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-first 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 ...
0
votes
0answers
23 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, ...
1
vote
1answer
41 views
A problem to maximize the number of edges in a cycle while minimizing the total weight
I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?
...
0
votes
0answers
16 views
Find a path passing through the minimum number of odd nodes [duplicate]
Assume you have a undirected graph where each vertex is marked either odd or even. Given two even nodes, How do you find the path that passes through the minimum number of odd nodes in O(edges)?
Now ...
1
vote
0answers
62 views
Algorithm for finding single input/output sub graphs
I'm running into an interesting directed acyclic graph (DAG) problem and was wondering if this is a known problem and if it has an efficient algorithm for it. I will use 'graph' and 'DAG' ...
0
votes
1answer
17 views
Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
0
votes
1answer
135 views
Finding topologically sorted connected components in directed acyclic graph
I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am ...
1
vote
1answer
36 views
Devising a way to spot a contradiction given a set of statements using graphs
If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John.
Would there be a way to figure out that there is a contradiction ...
0
votes
2answers
148 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 ...
4
votes
2answers
91 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 ...
1
vote
0answers
35 views
$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost
I have this problem
A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
13
votes
1answer
326 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 ...
1
vote
1answer
34 views
Shortest path in graph by flipping binary colored nodes to one color [closed]
Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the ...
1
vote
1answer
46 views
How to perform local search to find maximal induced subgraphs?
I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.
What I mean by local ...
1
vote
0answers
29 views
Order of Traversal in Bidirectional Dataflow Analysis
Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
0
votes
2answers
65 views
Quick and space-efficient way to find whether two sets intersect
I hope you can help me -
Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don'...
3
votes
2answers
70 views
When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?
The depth-first and breadth-first algorithms for traversing graphs use a flag (or color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. ...
3
votes
2answers
89 views
The complexity of the reachability-coreachability analysis of a finite state machine
Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is ...
1
vote
2answers
106 views
“Process functions” in iterative and recursive depth-first search
I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-...
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 ...
2
votes
1answer
224 views
Shortest path with a start vertex that touches all nodes at least once with repeats allowed
I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I ...
2
votes
2answers
80 views
Reduce the total internal border of a set of touching rectangles (using graphs)
I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
0
votes
2answers
240 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 ...
1
vote
0answers
71 views
Enumerate all re-convergent paths in a digraph (with cycles)
I'm looking for an algorithm to count and enumerate (separately, if differing complexity) all the reconvergent pathsets in a simple, directed, non-weighted graph, which may contain cycles. That is, ...
1
vote
1answer
637 views
DFS & BFS Spanning Trees
I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one.
DFS:
My understanding that to the ...
0
votes
2answers
258 views
How to traverse a graph in reverse with dfs
So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, ...
2
votes
2answers
152 views
Proof for BFS and DFS equivalence
I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.
Let $G$ be a directed ...
1
vote
1answer
51 views
proof that BFS remains total after adding edge to graph
I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$).
The inductive proof consists in 2 cases:
(i) Prove that $\rm{BFS}$$(u \in \...
1
vote
1answer
105 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 ...
1
vote
2answers
182 views
Is there a name for this graph search strategy?
The standard implementation of breadth-first search looks like
...
0
votes
2answers
75 views
Calculation of Inorder Traversal Complexity
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
3
votes
1answer
137 views
Understanding the “ordering of the four types of edges” in DFS
The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).
Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge ...
