Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
70
questions with no upvoted or accepted answers
13
votes
1answer
370 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 ...
7
votes
1answer
773 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
0answers
72 views
Find the 'best' longest common subsequence
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
5
votes
1answer
519 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
1answer
41 views
Computing a pre-topological sort using a BFS/a queue
Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes ...
4
votes
2answers
130 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
3k 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 ...
3
votes
2answers
572 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 ...
3
votes
0answers
68 views
Visiting all train stations
When I went to London, I wondered how to visit all the London Underground stations as fast as possible.
Given
a randomly-chosen start station,
timetable of train arriving & departing of every ...
3
votes
0answers
783 views
Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching
Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent.
The objective of the ...
3
votes
0answers
57 views
Heuristics to Find Circuits Allowing for Vertex Revists
I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem).
See: http://www.lancaster....
2
votes
0answers
43 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
93 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 ...
2
votes
0answers
334 views
How to traverse a graph in reverse dfs order
For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
2
votes
0answers
123 views
Algorithm to find nodes with given a distance
We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
2
votes
0answers
32 views
Inferences about Branching in TSP algorithm
I am building a program that uses branching-and-bounding to find an optimal path in a complete graph (the heuristic, faster algorithm is the second part). I have to begin and end at node 0. I was ...
2
votes
0answers
141 views
IDS algorithm optimality for grid?
My homework is implementing algorithms BFS, DFS, depth-limited and IDS for the map as a 2D grid with 8 directions of movement.
I read that the IDS algorithm is optimal, but in my case is not optimal ...
1
vote
0answers
17 views
Find all Eulerian cycles in a directed graph
I am trying to create an algorithm that can find all Eulerian cycles in a directed graph. I was able to make an algorithm that can find one cycle in the graph, but I don't know how to find all the ...
1
vote
0answers
120 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 ...
1
vote
0answers
75 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' ...
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 ...
1
vote
0answers
34 views
Order of Traversal in Bidirectional Dataflow Analysis
Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
1
vote
0answers
109 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
132 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
1answer
336 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 ...
1
vote
0answers
60 views
Dynamic path planning and waypoint sorting
Good evening everyone,
I have a question that I am having a bit of trouble formulating properly and thus it is making it complicated to look up literature on the subject. What I am looking for is a ...
1
vote
0answers
173 views
Efficient ways to avoid cycles in a graph
I am trying to implement an algorithm called the 'rapidly exploring random belief tree'. The aim of this algorithm is to come up with a path for a robot, which, instead of connecting start and goal ...
1
vote
0answers
144 views
How to systematically think about building implicit tree or a search space graph?
I often see DFS is used interchangeably with backtracking specially in many permutation, combinations and subset problems. But usually DFS has implicit tree and does backtracking at leaf nodes whereas ...
1
vote
0answers
307 views
Multithreaded algorithm to traverse DAG
I have a DAG of tasks designed as:
DAG {
Dictionary<NodeAddresses,Node>
}
Node {
List<Node> Parents;
List<Node> Children;
Task T;
}
...
1
vote
0answers
51 views
Pathfinding when the graph varies over time
Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi,...
1
vote
0answers
416 views
Dijkstras Algorithm with Bounded Integer Edge Weights
I don't really understand how we can use the fact that the edge weights are integers in the range [1, 2, ... , C] in order to speed up the computation of Dijkstra's algorithm. I read this lecture but ...
1
vote
0answers
58 views
Looking for name of siblings-first-depth-second traversal order
I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name.
The requirements of the algorithm are:
it visits the parent before the children.
it visits ...
1
vote
0answers
93 views
Node-weighted CSP in Prim's algorithm?
I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix:
$$
\left[ \begin{...
0
votes
0answers
20 views
Is there a Weisfeiler-lehman kernel for directed, labelled and with cycles graphs?
I have a set of labelled, directed and cyclic graphs and a I need to perform a supervised learning algorithm in this data.
I have found a single paper A Persistent Weisfeiler-Lehman Procedure for ...
0
votes
0answers
20 views
BFS vs DFS, and Timing of Marking Vertex as Visited
The Wikipedia article on Depth-Frist Search states that:
The non-recursive implementation is similar to breadth-first search
but differs from it in two ways:
it uses a stack instead of a ...
0
votes
1answer
55 views
binomial tree number of nodes
Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .
0
votes
0answers
18 views
Detecting whether a node belong to a cutset with the least memory consumption as possible
I'm working on a problem about connected components implemented by cutsets.
Given a cutset, I want to determine whether some node lies within the connected component created by such cutset. The most ...
0
votes
0answers
23 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 ...
0
votes
0answers
60 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 ...
0
votes
1answer
158 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 ...
0
votes
0answers
25 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++)
...
0
votes
0answers
101 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 ...
0
votes
0answers
31 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
0
votes
0answers
34 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
0answers
55 views
Whats the time complexity of Prims Algo. without heaps (using priority queue)?
Here's my attempt:
Initialisation -
...
0
votes
0answers
46 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, ...
0
votes
0answers
94 views
How many roots are there in an undirected root
Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
0
votes
0answers
17 views
Finding a path between 2 points passing through N points
Given a graph/plane with N points each at a given coordinate how could I find a path between 2 points via N other points where each point is weighted on how likely it is to be passed through.
...
0
votes
0answers
258 views
Longest-Path Layering algorithm
NOTES:
there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash.
the code provide in this post is python3 on the premise that it ...
0
votes
0answers
40 views
The path with the highest sum of weights
Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from ...
