Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
478
questions
0
votes
1
answer
23
views
Can Dijkstra's algorithm be used this way?
Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
2
votes
2
answers
108
views
A $O(|E||V|)$ algorithm to determine if a graph is singly connected?
In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem:
A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
- 67
0
votes
1
answer
52
views
Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time
In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
- 135
2
votes
1
answer
245
views
An efficient way to find a pair of unrelated edges
I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph.
Given a dense an ...
0
votes
0
answers
26
views
A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost
I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles.
We know that:
Dijkstra's algorithm uses ...
- 1
0
votes
0
answers
54
views
Question about implication in proof that predecessor subgraph is a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 67
0
votes
0
answers
31
views
Confusion about Lemma for Breadth-first search (BFS) proof of correctness
I'm working my way through the graph section of Introduction to Algorithms by CLRS (3E,4E) and I came across the following proof:
3E: Lemma 22.2
Let $G = (V, E)$ be a directed or undirected graph, and ...
- 67
0
votes
1
answer
25
views
Sign confusion in a BFS lemma
I have a confusion related the Lemma 22.1 in Cormen Leiserson Rivest Stein's Introduction to Algorithm book,
Here it is written that delta(s,v) <= delta(s,u) +1 ,where s,u,v are the vertices of a ...
0
votes
1
answer
53
views
What is the technical name for one sided tree traversal and which algorithms are good for it?
Looking at the image from Wikipedia page for tree traversal
what is the name for a traversal that follows the dashed line exactly with repeating visits to obtain: F, B, A, B, D, C, D, E, D, B, F, G, ...
- 103
1
vote
1
answer
85
views
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
The rural postman problem is:
Given a weighted MultiDiGraph $G=(V,E)$, a subset of ...
- 11
3
votes
1
answer
132
views
Number of "one neighbourhood" search trees in a graph
Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including ...
- 73
0
votes
1
answer
61
views
Checking if all nodes are reachable in a oriented graph from all other nodes
I'm having a lot of troubles understanding a preparation exercise about oriented graphs:
Consider the following game played on a directed graph G = (V, E) with
n nodes and m edges. A pawn is ...
- 103
1
vote
1
answer
49
views
Does graph traversal require stack machine?
I'm writing a graph traversal function to be used in a garbage collector.
To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and ...
- 192
0
votes
0
answers
39
views
Graph Search Algorithms that are practically fast on dense graphs
I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
2
votes
0
answers
99
views
On definitions of graph width
Wikipedia shows graph width $k$ as the degeneracy, an ordering of the vertices $v_1,\ldots , v_k$ for which, if we orient each edge $(v_i, v_j)$ towards $i$ where $i<j$, the maximal degree is at ...
- 435
0
votes
1
answer
100
views
How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?
How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices ...
- 11
0
votes
1
answer
29
views
Order list of lines to make them form a closed contour
I need to solve the following type of problem. I have a list of many connected lines forming a closed contour. These lines come as the output of a MarchingSquare algorithm. Consequently they are lines ...
- 5
1
vote
1
answer
78
views
Finding shortest path between two points in a polygon whose vertices are given?
A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
- 532
3
votes
1
answer
50
views
How to determine the largest number of disconnected arcs in a graph?
Given a directed graph $G=(V,E)$, I'm wondering if there's a way to determine the largest size of a set of edges that are disconnected pairwise. There is a similar problem for vertices (Maximum ...
- 31
1
vote
0
answers
336
views
Find the number of all possibilities to visit all vertices once in a connected graph
Let $G$ be a connected undirected graph, e.g.:
u -- v -- w
\ /
x
I would like to determine the number of sequences in which every vertex of the graph is ...
- 151
0
votes
2
answers
59
views
Can negative edge weights in a graph be positive numbers?
I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
- 149
0
votes
0
answers
56
views
Prove that BFS computes the shortest path from one vertex to another
I read in Algorithms in C by Sedgewick that we can easily prove by induction that breadth-first search algorithm computes the shortest path from one vertex to another (unweighted graphs or weighted ...
0
votes
0
answers
32
views
Directed graph where each node must contain all elements from source nodes
I'm looking for a directed graph data structure where each node is unique and contains a set of elements (at least one).
Each node must contain all elements from nodes pointing to it so it possible to ...
0
votes
1
answer
37
views
How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford
I want to find how many shortest paths are there from Node A to node B.
For example, let's say we have a graph with 3 nodes and 3 connections:
from 1 to 2 weight 5
from 1 to 3 weight 11
from 2 to 3 ...
1
vote
1
answer
54
views
How can we find a shortest closed walk passing through all vertices?
How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?
We allow vertices and edges to be repeated along the walk. The ...
- 303
1
vote
2
answers
68
views
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?
- 890
1
vote
1
answer
140
views
Find a weight threshold for edges for maximum number of connected components in a graph
So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
- 25
0
votes
1
answer
58
views
Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph
I am trying to research handling a specific type of possible subgraph in directed acyclic graphs.
However, I am struggling to find the correct term to use.
If we consider the subgraph S to be in a DAG ...
- 9
1
vote
1
answer
26
views
Route planning on line segments which can be connected or not
I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
- 111
3
votes
1
answer
111
views
Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...
Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
- 31
0
votes
1
answer
50
views
Calculate all distances in an undirected and unweighted graph
Which algorithm do I use and how much does it cost if I have to:
Calculate all distances in an undirected and unweighted graph from two sources to all nodes.
I think the most appropriate algorithm is ...
- 121
0
votes
1
answer
75
views
Directed weighted multigraph with dynamic edges - shortest path
I need to create an implementation of a directed weighted multigraph with dynamic edges:
The edges will be changing during the pathfinding, in the following way:
Summary of the pathfinding:
...
0
votes
0
answers
16
views
least collection of node disjoint paths that cover a given set of vertices
Given a directed graph G (with cycles) with source and target, and a set of interested vertices S.
we want to find a small n collections of vertice-disjoint-paths (path only have common nodes in ...
0
votes
1
answer
209
views
Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time
The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = ...
- 3
0
votes
0
answers
49
views
Observing when DFS outperforms IDS
I was thinking of a case where an IDS (Iterative Deepening Tree) always performs worse than a DFS (Depth-First Search). I have seen on numerous sources the example of a linked list(i.e. each node has ...
0
votes
1
answer
93
views
Set of all vertices in a directed tree that are within distance of strictly larger than 2
As the title says, I'm trying to solve the question where:
Input: A directed tree $T = (V, E)$.
Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u,...
- 11
0
votes
0
answers
36
views
The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)
What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
0
votes
1
answer
52
views
Is the traveling salesman on a map NP-hard?
It is known that the general traveling salesman problem is NP-hard. Even when the distances follow the triangle inequality. But let's take the problem very literally. There are actual cities (points) ...
- 305
0
votes
2
answers
193
views
Why compute finish time in topological sort
In depth first search each vertex can be associated with a discovery time and a finish time. I am reading the following implementation of topological sort in terms of depth first search
...
- 1
0
votes
1
answer
71
views
Determining all pixels of a specific color directly bordering on another color
I need a data structure/algorithm to efficiently retrieve borders and update changes.
There may be many (unconnected) regions of the same color. The shape of regions changes frequently over time and ...
- 191
1
vote
1
answer
33
views
Optimising updates to a way point graph
I have a graph of vertices and connected edges as shown in the image below.
I have a function that iterates from every single vertex and finds closed loops in order to find all polygons in the graph.
...
- 147
0
votes
1
answer
274
views
Proving why decreasing an edge weight in a graph may change it's MST by one edge
I'm working on understanding graphs and graph algorithms.
The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf
(Q 1.D)
Describe an efficient algorithm to ...
- 33
2
votes
1
answer
41
views
Finding optimal paths for multiple agents
This is a real world problem, which due to some specific aspects of it I am having a hard time finding relevant literature for it.
I am looking for either an algorithm, or a pointer to relevant paper(...
- 121
3
votes
1
answer
203
views
Getting all vertices with fixed index in their topological ordering of a DAG
During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve.
There are typically more than one order of a topological ordering ...
- 33
2
votes
2
answers
185
views
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 ...
- 71
0
votes
1
answer
40
views
How can ford fulkerson be explained concisely?
After going through the resource list, is the following a way to explain ford fulkerson concisely ?
Graphs is represent is a 2D matrix with flow capacity as a tuple in each cell.
...
- 95
0
votes
1
answer
44
views
Invariant in Kosaraju's algorithm for SCCs
I am studying graph algorithms, and I know that in algorithm theory there has to be an invariant of sorts that stays the same during the algorithm run that makes the algorithm valid and right to use. ...
- 15
0
votes
1
answer
566
views
0
votes
1
answer
128
views
Minimizing/Maximizing recursion depth for DFS
The idea for this problem comes from GATE CS 2014 Set-3 Q13.
Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth?
Consider the graph from ...
- 1,018
0
votes
1
answer
28
views
i am solving a question related to bfs traversal and there i got this doubt so can anyone plz solves this doubt?
if a BFS is applied on a graph is it necessary that the resultant BFS tree contains all the edges that are in the original graph ?