# Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

359 questions
Filter by
Sorted by
Tagged with
64 views

### Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck. Given a binary tree where each node in the tree can either be selected or unselected, ...
61 views

### Does DFS have better constants/complexity than Backtracking on a Graph?

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
27 views

### Understanding the proof of “DFS of undirected graph $G$, yields either tree edge or back edge” better with graph for each statement in proof

I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. ...
38 views

### Difficulty in understanding a portion in the proof of the $\text{“white path”}$ theorem as with in CLRS text

I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path ...
30 views

### Graph search or shortest path algorithm for graph with multiple “goals”?

I did a project in a class using A* search to solve an 8-puzzle. But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles. I’m not sure whether ...
45 views

### Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked ...
103 views

### Time taken by virus to reach all nodes

Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
44 views

### algorithm to find shortest path connecting EVERY node

I have received a problem to solve and I am not sure what algorithm to use. TLDR; Find the shortest path to get to every node in a undirected graph The problem states that one must visit every ...
64 views

### Calculating the structural integrity of a pixel grid

Preface So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been ...
60 views

### First-time and second-time seen edges in DFS on undirected graphs

Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on ...
30 views

37 views

### How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)

In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem: I have a set of ...
21 views

### Graph traversal problem touching every node exactly once

Is there a name for the problem: Suppose you have a connected, undirected graph; find a path that touches every node exactly once. This is basically the complement of the Hamiltonian Path problem, ...
36 views

### Is longest-path with a specific source and destination impossible in polynomial time?

The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a ...
37 views

### How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
62 views

### Understanding depth-limited BFS time complexity

I'm trying to implement graph power calculation using BFS. According to Wikipedia, BFS with depth limit k will suffice (I'm using adjacency list representation, my graphs are sparse, so adjacency ...
205 views

### Updating a mst after increasing the weight of an edge in the mst

Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$. I'm using a common ...
30 views

### Is there an algorithm for getting the boundary of a non-planar graph?

This is my first question here! If I have a non-planar graph where every vertex connects to 3 other vertices, and where the edges are allowed to intersect, how do I find the boundary of the graph? For ...
36 views

### How to find more than 1 successive shortest paths between two vertices in unweighted and undirected graph using BFS?

I have tried to find and print more than one successive shortest paths between two vertices in the undirected graph. Using BFS as DFS will not be optimal in this case, as it can go deep into the stack....
62 views

### Bridges and Edge Disjoint Paths

So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ? $\text{My Attempt at the Proof}$:- ...
20 views

### Why does this BFS solution work for this question about euclidean distance and what's its complexity?

Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector. ...
26 views

### Please explain the algorithm for finding bridges in graph?

let, low[] and disc[] be two 1D arrays disc[i] stores the discovery time of node[I] low[i] stores the lowest value between disc[i] and discovery time of children of node[i] I'm curious that what is ...
19 views

### Matching vertex values with sum of edge weights on bipartite graph

Earlier this week I asked this question (please review): Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags. ...
52 views

### Efficiently finding “unfounded edges” in a strongly connected graph

While implementing a debugger I've encountered a problem I need to solve concerning dependency graphs. I've simplified it as follows: Consider a strongly connected graph G = (V,E). We define a ...
42 views

### Finding a hamiltonianISH path in a graph

Problem statement Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions. Given any starting node. What ...
432 views

### Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive: ...
34 views

### small world networks properties

Small-world networks have two properties: clustering coefficient and average node-to-node distance my questions are: 1- Can a disconnected graph ( which may include multiple connected graphs) hold a ...
65 views

### In a DAG, finding the path with the highest score

Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a ...
36 views

### Number of m length walks from a vertice with steps in [1, s]

The problem is stated as the following: We are given a grid graph $G$ of $N \times N$, represented by a series of strings that describe vertices s.t. $L$ is the vertice we're interested in $P$ are ...
93 views

### Determine if there is a path with alternating edge colours in directed graph

Given directed graph $G = \langle V, E \rangle$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $v \in V$ if there is path from ...
56 views

### Graphs which favour BFS over DFS and vice versa

I am trying to figure out what kinds of graphs are better suited to BFS and which are better suited to DFS. However i'm struggling to visualise what kind of graphs favour which search. Could someone ...
24 views

### Restoring the minimum vertex cover on bipartite graph from the maximum matching

I had to solve a problem on finding the minimum vertex cover on a bipartite graph, and I used the Kőnig's theorem and reduced it to maximum matching problem on bipartite graph, which is easily ...
72 views

### Existence of walk in undirected connected graph where nodes must end with assigned value

We have a graph with $N$ nodes and $N-1$ undirected edges, where it's possible to reach one node from any other node. Each node will get assigned a value randomly from [1,...,10]. We want the value of ...
Problem: Given knight tour graph $G$ ($8 \times 8$ nodes) and a set of nodes $\{ v_{1}, v_{2}, \dots, v_{n} \} = V \subset V(G)$, find a minimal length tour in $G$ that visits all nodes from $V$ (...