Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
510 questions
2
votes
1
answer
107
views
How to find a bijection $\Phi$ that maximizes the number of iterative replacements in a local rewriting system on $\left\{ 0, 1, 2, 3 \right\}$?
Problem. We study a local rewriting map defined on $5$-letter words over the alphabet $\{0,1,2,3\}$. A fixed forbidden-block set $\mathcal{F}$ of $16$ length-$3$ patterns is given by
$$\mathcal{F}= \{...
- 111
2
votes
1
answer
105
views
Directed graph for a system of equations
I have a system of equations represented by a directed graph. Each node is a variable. Each edge is a "term dependency" that is a part of one equation. The graph is guaranteed to be ...
- 121
0
votes
1
answer
98
views
Dijkstra's Algorithm for Directed Graphs with Negative Edges Without Cycles
I came across a modified version of Dijkstra's algorithm that is said to handle graphs with negative edge weights, provided there are no negative cycles. I'm particularly interested in understanding ...
- 121
0
votes
0
answers
37
views
Is my implementation of the Richard Korf's bidirectional iterative-deepening depth-first-search (BIDDFS) correct?
This post is about correctness of the BIDDFS (bidirectional iterative-deepening depth-first search).
I got this idea from a Richard Korf's paper. Before answering, I suggest you first read this.
My ...
- 60
0
votes
1
answer
61
views
Does Reversing a Directed Acyclic Graph and Performing Post-Order Traversal Yield a Valid Topological Sort?
Reversing the post-order traversal (DFS) of a directed acyclic graph (DAG) results in a valid topological sort.
However, if we first reverse the graph (where every directed edge from ( u ) to ( v ) ...
- 121
3
votes
1
answer
99
views
Does the presence or absence of a second "discovered" check in iterative DFS matter?
Until April 2nd, the pseudocode on Wikipedia for iterative depth-first search was the following:
...
- 131
2
votes
1
answer
214
views
Find path in Directed Acyclic Graph from starting to ending node where each node is connected from an ancestor in the path
I am given a directed acyclic graph and I want to find all paths from a starting node to an ending node such that all child nodes are connected to previous ancestors. I'm not even totally sure how to ...
- 23
0
votes
1
answer
121
views
traveling salesman problem to time dependent traveling salesman problem
Everyone knows about the traveling salesman problem, but in most real world applications the time dependent traveling salesman problem is a much better model. Since most people seem to focus on the ...
0
votes
0
answers
30
views
Path-finding on a grid with multiple source-destination pairs and non-crossing paths
There is an infinite 2D square grid, every cell of which can be either empty or occupied by a wall. A path is defined by a sequence of moves either by 1 or 2 cells straight or by 1 cell in a diagonal ...
- 11
2
votes
1
answer
139
views
How to recover a COMPLETE binary tree from inorder, preorder or postorder traversal (uniquely! from only one traversal)
it's a common problem in CS/Data Structures/Graph Theory to recover a tree (or even binary tree) uniquely from a given set of inorder, preorder or postorder traversals. There is no method in general ...
- 41
2
votes
1
answer
269
views
A 2-coloring of a bipartite graph such that one of the partitions contains exactly k vertices
Given the efficient solvability of the $2$-coloring problem in bipartite graphs, I claim that the this problem can be accomplished within polynomial time.
A algorithm for solving this problem involves ...
- 83
0
votes
1
answer
74
views
Find the minimum number of send/recv actions in directed communication graph
Given p processes and n packages. Every process contains k = n / p distinct packages. Now, I ...
- 101
0
votes
0
answers
97
views
Graph Problem Time Complexity
I'm trying to devise an algorithm for the following prompt from LeetCode's daily challenge:
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[...
- 101
0
votes
0
answers
29
views
Escaping the cycle: Route planning in graphs with conditional edges
Given a directed graph $G(V, E)$, I want to find a route, $R \in E^*$ from $S$ to $T$ for $S,T \in V$. If $G$ includes a cycle, how can I find a route that includes $n$ iterations of the cycle before ...
1
vote
1
answer
103
views
Find the number of sink nodes per source node efficiently
My task is to write a function that, given a source nodes of a graph, returns the number of sink nodes (nodes with no outgoing edges) it reaches. The only access I have is to retrieve the neighbors of ...
- 13