Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
413
questions
0
votes
0answers
8 views
A DFS update without re-running DFS after adding and removing an edge
Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node.
...
0
votes
0answers
12 views
Detect the actual edges of circle in directed graph [duplicate]
Okay so , I know how bellman -ford can detect a negative circle.
My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
4
votes
1answer
36 views
How can we process these types of queries on trees?
CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS
I recently thought of this interesting Tree problem:
Given a tree with $N$ nodes, let $val_i$ = the "value" for ...
6
votes
1answer
79 views
Archaeological Consistency: Graph Problem
So, I have an issue with the following problem (CS 161 Stanford 2013, Problem Set 2):
Suppose that you have found a collection of historical records indicating the relative order in
which various ...
0
votes
1answer
77 views
modify dfs to find longest path
Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$.
For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
1
vote
1answer
66 views
Shortest walk from $u$ to $v$ through $w$
We have an undirected, weighted graph $G=(V, E)$ with two weight functions
$W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$
such that for every $e \in E$ we have $W_1(e) &...
0
votes
1answer
56 views
How can it be proved that two different kinds of dfs unequivocally define a unique tree?
How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a ...
0
votes
2answers
62 views
finish time of vertex in DFS
Will u.f and u.d of a vertex in DFS traversal change if we change order of vertices in adjacency list ? I know that u.d won't change but what about u.f?
u is a vertex of the graph.
u.f, u.d are ...
2
votes
0answers
22 views
Tree search algorithm to find optimal terminal node
I have a few board games where in each round one can do a set of action. Depending on the previous actions, the set of possible actions is different. Usually after a fixed amount of rounds, the game ...
1
vote
0answers
17 views
Visiting vertices on a graph using DFS and BFS
I have this graph that I created and am wondering how DFS and BFS would work on something like this. I made this graph undirected and am going off the premise that if possible, a vertex should be ...
1
vote
0answers
66 views
How to find the shortest path that visits all nodes of a non-complete graph (repeating nodes allowed)?
Let $G$ be a non-complete weighted (only positive weights) undirected connected graph. I'm trying to find a path such that it visits all nodes at least once (repeating nodes is allowed), and it's the ...
2
votes
1answer
69 views
Why recording non-existent children in the pre-order traversal will differentiate different binary trees?
I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can ...
1
vote
0answers
28 views
Social Networking Disease Transmission
You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$
met at some point during ...
0
votes
0answers
31 views
Traversal algorithm for an optimal item collecting route in the game "Eternal Return: Black Survival"
I am currently trying to implement a algorithm for the game "Eternal Return: Black Survival" as a kind of exercise in Rust.
Since the game may not be familiar to many, here is a quick ...
1
vote
1answer
29 views
Meaning of source here
In graph theory, a source of a directed graph $D = (V(D), E(D))$ is a vertex of it whose in-degree is zero.
The book CLRS makes these statements:
Given a graph $G = (V, E)$ and a distinguished source ...
3
votes
1answer
45 views
Comparing different versions of Steiner Connected Component Subgraph problem
Problem 1
Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected ...
1
vote
0answers
61 views
Square of a directed graph $G=\left< V, E\right>$
I have this question from CLRS book please.
Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2 $ iff for some ...
2
votes
1answer
53 views
Are recursion and a stack equivalent in terms of inplementing DFS?
It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem:
...
4
votes
2answers
100 views
Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?
This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing ...
2
votes
1answer
161 views
Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)
Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
2
votes
2answers
80 views
Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$
Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it.
...
0
votes
0answers
32 views
Finding the shortest distance between two nodes given multiple graphs
Assume that we have a set of nodes and multiple graphs with different edge values for the same set of nodes. As an example, there are 4 nodes A, ...
3
votes
0answers
31 views
Shortest path which passes through a subset of vertices in an unweighted directed graph [duplicate]
Given an unweighted directed graph $G=(V, E)$, two vertices $s,t \in V$ and a subset of vertices $U \subseteq V$, suggest an algorithm which concludes if there exists a shortest path from $s$ to $t$ ...
0
votes
1answer
39 views
Can someone explain intuitively why union find works to find a cycle in an undirected graph?
I understand how the UF algorithm works to detect a cycle in an undirected graph, but I don't understand why it always works. Could someone explain that intuitively?
Specifically, I don't understand ...
2
votes
1answer
37 views
Finding an optimal solution in a tile painting game
The Problem
Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal solution, just find one of them.
Game Rules
The game level is made up ...
0
votes
1answer
213 views
When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?
This seems to be my first ever question :)
Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that.
I don't ...
1
vote
0answers
23 views
How long a graph random walk takes to hit every vertex?
I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step.
On average, how ...
0
votes
1answer
35 views
Path connecting certain vertices in a neural graph
Consider a special kind of graph where the nodes can be partitioned into $n$ layers. There are edges only between successive layers and no edges between the nodes of any given layer. So for example, ...
2
votes
0answers
45 views
Constrained/Optimal Topological Order to enhance/reduce the performance/memory usage of other algorithms
I originally posted this question here
Lets assume we have a highly connected directed acyclic graph (DAG, more edges then nodes). Since it is a DAG, we can retrieve a topological order of nodes to ...
1
vote
1answer
83 views
Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?
I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me):
Vector-representation based models. One naive approach would be to represent G by flattening ...
2
votes
0answers
32 views
Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)
We have an algorithm problem in hand, can you please write your ideas about this, thank you!
There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
1
vote
1answer
33 views
Non-brute force algorithm for a Eulerian like path
I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one ...
2
votes
1answer
382 views
Shortest path given correct order of colours?
I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, ...
0
votes
2answers
84 views
Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?
I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.
For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with ...
2
votes
3answers
346 views
find a path to visit every node in graph not necessarily once
I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)?
This problem is different from Hamiltonian ...
2
votes
1answer
39 views
Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?
My understanding of non-deterministic algorithms is that they're "as lucky as you want".
...you can think of the algorithm as being able to make a guess at any point it wants, and a space ...
1
vote
1answer
32 views
Number of paths starting from a given edge using adjacency matrix
I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that ...
0
votes
1answer
127 views
Stack without duplicates
I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during ...
2
votes
2answers
59 views
algorithm for connectivity by path of given length
Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm ...
2
votes
0answers
178 views
How to quickly determine whether a poset is a lattice?
Recently I encountered an interesting problem while studying discrete mathematics:
Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the ...
1
vote
2answers
106 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
142 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
142 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
159 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
99 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
21 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
36 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
191 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
102 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
89 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 ...
