Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
424
questions
2
votes
2
answers
83
views
Are reversed reverse preorder traversals equivalent to a postorder traversal?
I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse ...
- 123
0
votes
1
answer
39
views
Walk from vertex u to vertex v on complete graph, formula for number of walks of length k
Complete graph with n vertices.
Walk from vertex u to vertex v of length k.
I don't understand how the number of walks between the two of length k is $n^{k-1}$
I've tried this formula on an example ...
- 13
0
votes
0
answers
10
views
Approach for flattening a 3-d cube given cuts
Take a cube. Cut seven of its edges. Consider a graph whose vertices are the centers of the faces of the cube. If two faces share a common edge, then the graph also has an edge connecting the two ...
- 305
0
votes
0
answers
23
views
Using an undirected graph to represent an ordered pair?
Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
- 175
6
votes
1
answer
363
views
What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?
I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such ...
- 305
2
votes
1
answer
28
views
Make maze connected by removing internal walls
Recently I've stumbled upon a strange graph problem. Here is a brief description.
Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-&...
- 123
1
vote
0
answers
113
views
Min weighted path in a graph, but you could die
The min-path problem is mostly motivated by a graph with cities as vertices and roads between them as edges. Each edge has a weight which could be the length of the road or the time it takes to cross ...
- 305
0
votes
1
answer
45
views
Algorithm to find for each vertex, a vetrex that it can reach with the lowest cost in a graph
We have a directed graph $G=(V,E)$ and each vertex $v\in V$ has a cost: $price(v)$. Our mission is to find an algorithm that runs in time $\mathcal{O}(|E|+|V|)$ that finds $\forall v\in V$ the minimal ...
- 103
2
votes
0
answers
37
views
Finding a circle within a circle
Let $G=(V,E)$ be undirected, and let $s,t\in V$ and $C\subseteq E$ be a circle that contains $s$ and $t$. Assuming $s$ and $t$ are on the circle $C$, we are given a set of edges $F\subseteq E$ which ...
- 1
1
vote
0
answers
26
views
Node domination in constrained path search
It's possible to modify a graph search algorithm such as Dijkstra's or A* to allow for non-additive objectives or constraints. Is there a standard treatment for these algorithms to reduce unnecessary ...
- 222
0
votes
0
answers
13
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
0
answers
13
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 ...
- 191
4
votes
1
answer
47
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 ...
- 425
6
votes
1
answer
87
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 ...
- 163
0
votes
1
answer
341
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 ...
- 25
1
vote
1
answer
78
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) &...
- 21
0
votes
1
answer
58
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 ...
- 17
0
votes
2
answers
189
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 ...
- 75
2
votes
0
answers
26
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 ...
- 171
1
vote
0
answers
27
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 ...
- 21
1
vote
0
answers
77
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 ...
- 161
2
votes
1
answer
80
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 ...
- 31
1
vote
0
answers
29
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 ...
- 23
0
votes
0
answers
45
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
1
answer
30
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 ...
- 377
3
votes
1
answer
50
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 ...
- 2,851
1
vote
0
answers
69
views
Square of a directed graph $G=\left< V, E\right>$ [closed]
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 ...
- 459
2
votes
1
answer
66
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:
...
- 1,071
4
votes
2
answers
141
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 ...
- 43
2
votes
1
answer
200
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: ...
user135193
3
votes
2
answers
119
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.
...
- 203
0
votes
0
answers
38
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
0
answers
32
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$ ...
- 203
0
votes
1
answer
63
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 ...
- 111
2
votes
1
answer
53
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 ...
- 21
1
vote
3
answers
488
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
0
answers
27
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 ...
- 389
0
votes
1
answer
37
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, ...
- 305
2
votes
0
answers
58
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 ...
- 21
1
vote
1
answer
87
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,910
2
votes
0
answers
34
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 ...
- 21
1
vote
1
answer
44
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 ...
- 11
2
votes
1
answer
411
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}, ...
- 123
0
votes
2
answers
106
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 ...
- 934
2
votes
3
answers
489
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 ...
- 123
1
vote
1
answer
44
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 ...
- 351
1
vote
1
answer
42
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
1
answer
166
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 ...
- 7,154
2
votes
2
answers
65
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 ...
- 123
2
votes
0
answers
213
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 ...
- 21