Computer Science Stack Exchange
Computer Science Stack Exchange

Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

489 questions
3
votes
1 answer

Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths?

I am curious of knowing of an efficient algorithm for the problem: Given two vertices s,t in a directed graph, is there a vertex x such that xs and xtare paths? I can of course do a BFS from each node of the graph resulting in a quadratic time…
user695652
  • 783
  • 1
  • 5
  • 14
2
votes
1 answer

Restricted traversal on an undirected graph

Given a undirected graph $G=(V,E)$. Imagine traversing the Graph was restricted; following an edge $a$ over a node $v$ to an edge $b$ is allowed if and only if a function $w: ( a, v, b ) \rightarrow \{0,1\}$ returns $1$. Is there a effective…
Rodney Merrick
  • 23
  • 3
2
votes
2 answers

Does it require O(|E|) time to visit all nodes?

In an undirected graph it takes $O(|V| + |E|)$ time to visit all nodes in a simple graph using BFS according to our lecture notes. But why can't you visit them all in $(|V|)$ time instead?
Simd
  • 996
  • 5
  • 17
2
votes
2 answers

Find the shortest path from a set of source points to the nearest source/destination point

I have a graph data structure that has some source points (the red ones) and some destination points (the blue ones). I want to find the shortest path from every source point to its nearest destination point, or to its nearest source point that is…
devfaz
  • 71
  • 4
2
votes
0 answers

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 is finished and one computes the total number of…
Martin Ueding
  • 171
  • 1
  • 4
1
vote
1 answer

Prove that the depth of every vertex in a cycle is $\le \lfloor \frac{n}{2} \rfloor$ in a breadth first search?

Suppose I have an undirected graph that consists only of a cycle. Each vertex has a depth value that must be $1$ greater than its predecessor (i.e. if we reach vertex $F$ from vertex $C$ which has a depth of $2$, then $F$ has a depth of $3$). The…
Chris
  • 125
  • 2
1
vote
0 answers

Satisfy edges' constraints when updating node in directed acyclical graph

I have a directed acyclical graph. Each node represents an event with start and end dates and each edge represents a constraint between to events with 2 properties: max interval between previous event end and next event start min interval between…
package
  • 111
  • 1
1
vote
0 answers

How to efficiently calculate the longest road in catan?

In Catan you can calculate the longest road by finding the longest (most roads) path which does not repeat any edges/roads, and does not cross through a vertex controlled by another player. I started doing an algorithm that: sorts the roads into…
Bovard
  • 111
  • 3
1
vote
1 answer

BFS vs DFS, and Timing of Marking Vertex as Visited

The Wikipedia article on Depth-Frist Search states that: The non-recursive implementation is similar to breadth-first search but differs from it in two ways: it uses a stack instead of a queue, and it delays checking whether a vertex has been…
Nicolas Miari
  • 109
  • 3
0
votes
1 answer

Find all sets of nodes that can be connected with a single path

** Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck. Say I have an undirected graph. I would like to find all possible…
Aart Stuurman
  • 101
  • 4
0
votes
1 answer

Sorting post numbers in a graph in $O(n)$ time

After running dfs on a graph, we get a list of n post and pre numbers. How do we sort this list in $O(n)$ time instead of $O(n\log n)$ time?
matt
  • 147
  • 3
0
votes
2 answers

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 finish and discovery times of the vertex u…
user145450
0
votes
1 answer

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 so any help on how I could do so would be…
SD8
  • 1
0
votes
2 answers

Graph theory: BFS (Breadth First Search) - why is current processed first?

I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn't "breadth first" mean "Process children first, then process parent"? or, is that only for…
eric frazer
  • 101