Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
380
questions
1
vote
2answers
83 views
Proving that a preorder traversal of a rooted tree can be performed in linear time
Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \...
2
votes
0answers
31 views
Optimal Item Locations given Traversal Paths
I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations.
Additionally, I have a ...
0
votes
1answer
34 views
Create Shortest Path tree for every node after Floyd Warshall in O(nm)
Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
1
vote
1answer
24 views
Longest path in a strongly connected component
So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.
My idea is: In a strongly connected component ...
0
votes
1answer
73 views
Each cycle in the graph, the edge with the minimum weight belongs to MST
Let $G=(V,E)$ be a weighted undirected connected graph and $w: E \to \mathbb{R^{+}}$ a weight function so that there are no two edges that have the same weight, and $T$ is an MST of $G$ . Then in ...
0
votes
0answers
13 views
Finding time complexity of a depth first traversal algorithm with a depth limit to get all node traversals starting from the root node
What would be the time complexity of a depth-first traversal algorithm on a graph, that is simply trying to retrieve all nodes being visited from starting node up until a depth limit is reached (i.e. ...
1
vote
0answers
34 views
What does “yields” mean in the phrase *yields no back edges* in DFS?
What does yields mean in the phrase yields no back edges in the context of DFS?
...
1
vote
1answer
83 views
What does Dijkstra's algorithm become, when you replace path cost with edge cost?
Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are ...
1
vote
1answer
28 views
How does node expansion work in a graph for AI search?
I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city ...
3
votes
1answer
62 views
Trapezoidal decomposition of a graph
When we plan the motion of a robot we may apply the trapezoidal
decomposition of free space. While applying the trapezoidal
decomposition we add nodes to both the centers of trapezoids and
vertical ...
1
vote
0answers
27 views
Simultaneous binary (n-ary) search
I have a balanced $k$-ary B-tree with $N$ leaves (where N is a power of $k$ for simplicity) and I need to simultaneously locate $\ell$ leaves in it. What is the expected number of nodes I will need to ...
0
votes
2answers
38 views
Route finding on a graph that must go through multiple edges
I have this graph
It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
0
votes
0answers
14 views
Can anyone explain how look-up tables are used for optimal Rubik's cube solvers such as Thistlethwaite's or Kociemba?
I have implemented Thistlethwaite's algorithm however, it is far too slow as it is only using graph traversal over many Rubik's cube states. I am currently unsure of how look-up tables are implemented ...
1
vote
1answer
55 views
Question about the conditions to find articulation points in a graph
I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.
In it, we first ...
0
votes
1answer
36 views
Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree
CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have
...
0
votes
1answer
22 views
Floyd Warshall with constraints
I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths ...
1
vote
1answer
61 views
Can the loops be in any order in the Floyd-Warshall algorithm?
I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:
...
0
votes
0answers
43 views
For every node of a tree, find the nearest ancestor node such that val[node] is coprime to val[ancestor]
Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note ...
1
vote
0answers
18 views
Greedy Best-First Search Performance for Tree and Graph Space
I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being
not optimal in Tree Search for Finite and Infinite Spaces
that it is ...
1
vote
1answer
29 views
For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X
For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two ...
1
vote
1answer
10 views
Circular path visiting fewest nodes
I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good ...
0
votes
1answer
19 views
speed of preorder traversal
I want to know the speed of preorder traversal of an tree. I do not mean its order of magntude which we know is O(n).
I want something like 27n operations where an operation is precisely defined.
...
0
votes
0answers
18 views
Why we take decreasing order of finishing times and NOT increasing order of discovery times in kosaraju algorithm?
We take decreasing order of finishing times in $G^t$ (transpose of Graph G) to know whther the path exists in other direction as shown below. But why can'nt WE take increasing order of discovery time ...
2
votes
0answers
33 views
Counting paths by their type
An edge-labelled directed graph is the data of $G = (V, E, l)$ where $(V, E)$ is a directed graph, and $l \colon E \to \mathbb{P}$ is some function. (For the graph I am considering, labels take values ...
0
votes
0answers
43 views
Complexity of Finding Every Cycle in a Graph?
What's the best asymptotic complexity of finding every cycle in a simple, directed graph?
I haven't been able to find anything regarding this online. I'm able to use DFS for cycle detection, but I'm ...
0
votes
1answer
35 views
How can I examine the subnetworks of a nearly fully connected graph?
I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a ...
0
votes
0answers
32 views
Question regarding a particular type of graph
Let $G = (V,E)$ be a directed graph where every vertex is represented by an $n$ bit string. The edges are represented by two polynomial-sized circuits $S$ and $P$. There is an edge from $u$ to $v$ if ...
0
votes
0answers
40 views
Graph algorithm to group nodes by level and group size
I have a directed graph representing some topics organized as follows (below screenshot is a subset of the graph):
I'm looking for an algorithm to group a set of nodes (in blue in the diagram) ...
2
votes
0answers
83 views
Minimum number of nodes to select such that every node is at most k nodes away
I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck.
Given a binary tree where each node in the tree can either be selected
or unselected, ...
1
vote
2answers
227 views
Does DFS have better constants/complexity than Backtracking on a Graph?
I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
1
vote
0answers
66 views
Understanding the proof of “DFS of undirected graph $G$, yields either tree edge or back edge” better with graph for each statement in proof
I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. ...
1
vote
1answer
51 views
Difficulty in understanding a portion in the proof of the $\text{“white path”}$ theorem as with in CLRS text
I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path ...
2
votes
2answers
108 views
Graph search or shortest path algorithm for graph with multiple “goals”?
I did a project in a class using A* search to solve an 8-puzzle.
But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles.
I’m not sure whether ...
2
votes
1answer
84 views
Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS
I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked ...
3
votes
0answers
112 views
Time taken by virus to reach all nodes
Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
0
votes
1answer
97 views
algorithm to find shortest path connecting EVERY node
I have received a problem to solve and I am not sure what algorithm to use.
TLDR; Find the shortest path to get to every node in a undirected graph
The problem states that one must visit every ...
2
votes
1answer
95 views
Calculating the structural integrity of a pixel grid
Preface
So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been ...
4
votes
1answer
81 views
First-time and second-time seen edges in DFS on undirected graphs
Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on ...
2
votes
2answers
33 views
Label groups of vertices in a graph in an efficient manner without BFS/DFS
I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in ...
1
vote
1answer
27 views
How can follow this this guide to construct a graph with matrix/reachability
Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
1
vote
0answers
28 views
Finding the lengths at which cycles exist in a graph in parallel
I'm trying to find an algorithm that can find the lengths of simple cycles in an undirected graph in parallel that benefits strongly enough from it's parallelization to be practically more efficient ...
0
votes
0answers
27 views
2 Questions about Topological sorting in DAG
$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$.
...
0
votes
0answers
18 views
ways to rearrange a closed graph with cycles
Let's say we have the following graph defined by its initial node, final node, and edges in a transition table:
what are the possible ways to rearrange this data structure in order to have something ...
4
votes
1answer
54 views
Connect a graph
Given an undirected graph, We need to convert it into a connected graph by adding/removing the edges keeping the summation of absolute difference of change in degree of nodes minimum.
There can be ...
1
vote
2answers
137 views
Finding the shortest path in a grid which has walls
The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a ...
1
vote
1answer
27 views
Path uniqueness in undirected graph
Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count.
...
2
votes
1answer
89 views
Name of BFS variant with multiple queues with different priorities
Is there a name for the following variant of BFS that operates on trees with non-root starting point?:
Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
1
vote
1answer
40 views
Product of all nodes except for one in Binary Tree
Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...
0
votes
0answers
25 views
Does this algorithm traverse trees in logspace?
Does this algorithm traverse trees (correctly) in logspace?
Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
1
vote
1answer
145 views
What's the name of this DFS variation
Classical DFS:
A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic.
A DFS ...
