Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
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 ...
Johnny Upman's user avatar
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$ ...
Hugh Mann's user avatar
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 ...
maplemaple's user avatar
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 ...
Benicio Agüero's user avatar
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 ...
Math98's user avatar
  • 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, ...
Hugh Mann's user avatar
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 ...
Hugh Mann's user avatar
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 ...
Ibtida Bin Ahmed's user avatar
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, ...
MathX's user avatar
  • 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 ...
somewhere's user avatar
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 ...
YoloV4's user avatar
  • 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 ...
JayK23's user avatar
  • 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 ...
DannyNiu's user avatar
  • 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 ...
sharkeater123's user avatar
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 ...
Eric_'s user avatar
  • 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 ...
IsalanOnkar's user avatar
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 ...
aSpagno's user avatar
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 $...
chausies's user avatar
  • 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 ...
underdog987's user avatar
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 ...
Bob Aiden Scott's user avatar
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 ...
Daniel's user avatar
  • 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 ...
hcentenaro's user avatar
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 ...
alphashock's user avatar
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 ...
ViktorMaksimoski's user avatar
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 ...
licheng's user avatar
  • 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?
Simd's user avatar
  • 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 ...
Tomyy's user avatar
  • 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 ...
T-Tory's user avatar
  • 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 ...
GPrathap's user avatar
  • 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 ...
aurel1510's user avatar
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 ...
emacos's user avatar
  • 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: ...
discrete coder's user avatar
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 ...
Yufei Zheng's user avatar
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 = ...
Mikey's user avatar
  • 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 ...
Green Ideology's user avatar
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,...
Salty Champ's user avatar
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? (...
AmirHosein Adavoudi's user avatar
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) ...
Rohit Pandey's user avatar
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 ...
shark's user avatar
  • 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 ...
2080's user avatar
  • 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. ...
WDUK's user avatar
  • 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 ...
DarkCave's user avatar
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(...
Itamaram's user avatar
  • 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 ...
DarkCave's user avatar
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 ...
devfaz's user avatar
  • 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. ...
New Student's user avatar
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. ...
mrbelyash's user avatar
0 votes
1 answer
566 views

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

CLRS pseudocode: ...
mimmolg99's user avatar
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 ...
Rinkesh P's user avatar
  • 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 ?
Shikhar Joshi's user avatar

1
2 3 4 5
10