Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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 "+", "-&...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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) &...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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. ...
user avatar
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, ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
9