Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
5
votes
1answer
449 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
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 ...
13
votes
0answers
297 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 ...
5
votes
0answers
697 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, ...
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
724 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
56 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
294 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
105 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
124 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
69 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
61 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
34 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
28 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
60 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
0answers
45 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
120 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
127 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
284 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
356 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
56 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
89 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
26 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
31 views
Whats the time complexity of Prims Algo. without heaps (using priority queue)?
Here's my attempt:
Initialisation -
...
0
votes
0answers
15 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
14 views
Alternative technologies/theories for a “Git for Structured Graph Databases”
Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...
0
votes
0answers
239 views
A longest path can be found using DFS
The following is a Yes/No question. In an undirected unweighted graph $G$, a longest path between two given
vertices $s$ and $t$ can be found using Depth-first search?
If it is possible to use DFS
...
0
votes
0answers
56 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
14 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
192 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
39 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 ...
0
votes
0answers
68 views
Multi agent graph traversal with edge discovery
Suppose we are given a set of agents (say $P_1 , \dotsc, P_M$), an undirected graph G(V,A) and a set of initial vertices on $G$ where each agent is located. Initially only the edges connected to these ...
0
votes
0answers
95 views
Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder
I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
0
votes
0answers
991 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 ...
0
votes
0answers
132 views
Distance of a Graph node to a group of nodes?
Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity ...
0
votes
0answers
180 views
Efficient algorithm to find an vertex that is not an articulation vertex
This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201.
Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion ...
0
votes
0answers
37 views
Finding continuous line consisted of points surrounding points of different color
I have a problem with creating an algorithm that would find continuous line consised of points of one color (say blue) that surrounds points of different color (say red).
This problem occurs in "Dots"...
0
votes
0answers
306 views
What is the time and space complexity of unidirectional bfs and bidirectional bfs?
How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?
0
votes
0answers
442 views
Finding a path visiting most nodes in complete digraph with cost limit and positive or negative edge weights
I'm leaving out some specifics because this is a challenge problem and I don't want to be spoon-fed the answer, but I need a nudge in the right direction.
I am given a complete digraph with the ...
0
votes
0answers
245 views
Making DFS more efficient
I was looking for non-recursive implementation of DFS algorithm.
I found the following pseudocode on this page.
...
0
votes
0answers
33 views
How to choose the maximum vertices you can delete from set while atleast 1 of its neighbors is in set?
We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected:
...
0
votes
0answers
163 views
What is the algorithmic complexity of DFS under the cache oblivious model?
Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size &...
0
votes
0answers
553 views
Traveling Salesman problem solution for small graph?
So let's say i have a graph like this and salesman starts his journey at "A"
How do i solve the TSP problem for this graph with pen and paper on exam?
0
votes
0answers
461 views
Fastest Algorithm to find shortest path between two edges in a graph
If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)?
I am trying to answer a question in the EPI book. ...
0
votes
0answers
46 views
optimal path for traversing nodes
So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least ...
0
votes
0answers
554 views
Failing to understand the pseudo code of the inorder traversal
Edit: Solved, see comments
I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is:
...
0
votes
0answers
152 views
Generalized steps to find tree traversal for any m-ary tree
So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I ...
0
votes
0answers
479 views
Hopcroft–Karp algorithm time complexity
In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph:
https://dl.dropboxusercontent.com/u/64823035/04569670.pdf
The ...
