# Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

478 questions
Filter by
Sorted by
Tagged with
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 ...
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$ ...
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 ...
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 ...
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 ...
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, ...
31 views

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 ...
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 ...
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, ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
78 views

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? (...
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) ...
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 ...
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 ...
1 vote
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. ...
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 ...
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(...
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 ...
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 ...
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. ...
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. ...
566 views

### Why is the complexity of BFS O(V+E) instead of O(V*E)?

CLRS pseudocode: ...