# Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

502 questions
Filter by
Sorted by
Tagged with
3 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
40 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 ...
112 views

### Are there theorem dual to Tarjan's theorem for breath first search?

In "Depth-First Search and Linear Graph Algorithms" Tarjan proposed following theorem as the foundation of depth-first search (rephrase a little bit): Let $G=(V,E)$ be a connected (...
• 141
14 views

### Calculating the most influential set of source nodes on a target node when a source node's signal is propagated

I am mainly posting for guidance, as I don't know where to start looking in order to solve the following problem: Given a directed graph G with edge weights between 0 and 1. As well as a set of ...
32 views

### What is this graph?

I am seeking nomenclature to describe the family of graphs detailed below, and literature about its processing, traversal, costs, etc. Any and all input is welcome, e.g. papers, textbooks, helpful ...
• 111
1 vote
49 views

### Find the transitive closure but with a twist

Situation I have a set of set of elements V, and relations over V: a R b: "a is related to b" (reflexive and symmetrical) a N b: "a is not related to b" (anti-reflexive and ...
• 229
1 vote
47 views

### BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
• 11
65 views

### Finding Common Neighbors between Graph Nodes

I am working on an Application that will generate a graph where each node is either a disease or its symptom. This is an undirected graph, and there is an edge between the disease and its symptoms. ...
95 views

### Find best path in an alternating graph

I am trying to solve the following problem: Given a directed graph, there is a robot in the start and it needs to reach the destination. Each movement takes 1 second, and every second the graph ...
• 21
19 views

### all pairs shortes path variant [duplicate]

Let $G=(V,E)$ a directed Graph with a coloring function $F:E \to red,blue$ and a weight function $W: E \to R$ I need to find all pairs shortest path s.t. every path visits at least one red edge, or ...
17 views

### How to get the iterator of the ancestor nodes during DFS or BFS?

I am able to solve this by myself, but somebody may already know the answer, so saving manpower, instead of me probably trying several variants. What is an easy way during either DFS or BFS of a DAG ...
• 503
756 views

### What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
• 503
46 views

### Why is the Time Complexity of DFS Algorithm O(|V| + |E|) instead of O(|E|)?

I'm trying to understand time complexity in the context of graph algorithms, especially Depth-First Search (DFS). As far as I understand, time complexity indicates how the execution time of an ...
92 views

### DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
• 123
1 vote
27 views

### Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks. For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this... Mitutoyo's 56 ...
84 views

### Graph labyrinth solving sequence

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
1 vote
78 views

### How to find largest caterpillar in a tree

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, ...
• 11
1 vote
32 views

### Proving that Breadth-First Search (BFS) results in a bipartition of a tree

In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that ...
1k views

### Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met: Upon removing any arbitrary node, the total weight of nodes in each ...
103 views

### DFS to assign guards to nodes in a tree structure

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum ...
• 67
1 vote
191 views

### 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 ...
• 111
310 views

### Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig. what to prove about the general "graph search": (Here I assume "within ...
• 203
60 views

### Graph containing a cycle of $2k$

Given an undirected graph $G=(V,E)$, and a parameter $k\in \mathbb{N}$ such that $k\geq 2$, how can I show that if $|E|\geq |V|^{1+\frac{1}{k}}$, a cycle $C$ exists in $G$ such that $|C|\leq 2k$? The ...
• 534
151 views

### Negative cycle of even length

Given an undirected graph $(V,E)$ with weights on edges $\in Z$ is it possible to find a negative cycle of even length (not the weight of the cycle, but the number of edges contained in the cycle) in ...
1 vote
86 views

### Finding the pair of nodes with maximum distance in an arbitrary rooted tree

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, ...
1 vote
102 views

### Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
• 113
1 vote
135 views

### number of edges that appeared at least in one shortest path

In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices. ...
1 vote
115 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 ...
182 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$ ...
81 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 ...
• 145
247 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 ...
41 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 ...
61 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, ...
46 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 ...
30 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 ...
59 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
111 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 ...
140 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 ...
• 83
219 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
65 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 ...
• 352
58 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 ...
102 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 ...
• 485
123 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 ...
50 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
186 views

84 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