Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
2
votes
0answers
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, ...
0
votes
2answers
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 ...
1
vote
0answers
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. ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
2answers
30 views

Label groups of vertices in a graph in an efficient manner without BFS/DFS

I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in ...
1
vote
1answer
25 views

How can follow this this guide to construct a graph with matrix/reachability

Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
1
vote
0answers
28 views

Finding the lengths at which cycles exist in a graph in parallel

I'm trying to find an algorithm that can find the lengths of simple cycles in an undirected graph in parallel that benefits strongly enough from it's parallelization to be practically more efficient ...
0
votes
0answers
24 views

2 Questions about Topological sorting in DAG

$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$. ...
0
votes
0answers
16 views

ways to rearrange a closed graph with cycles

Let's say we have the following graph defined by its initial node, final node, and edges in a transition table: what are the possible ways to rearrange this data structure in order to have something ...
4
votes
1answer
53 views

Connect a graph

Given an undirected graph, We need to convert it into a connected graph by adding/removing the edges keeping the summation of absolute difference of change in degree of nodes minimum. There can be ...
1
vote
2answers
81 views

Finding the shortest path in a grid which has walls

The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a ...
1
vote
1answer
25 views

Path uniqueness in undirected graph

Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count. ...
2
votes
1answer
44 views

Name of BFS variant with multiple queues with different priorities

Is there a name for the following variant of BFS that operates on trees with non-root starting point?: Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
1
vote
1answer
34 views

Product of all nodes except for one in Binary Tree

Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node ...
0
votes
0answers
25 views

Does this algorithm traverse trees in logspace?

Does this algorithm traverse trees (correctly) in logspace? Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
1
vote
1answer
131 views

What's the name of this DFS variation

Classical DFS: A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS ...
2
votes
2answers
55 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
0
votes
0answers
21 views

Could this be used to find the largest path in a graph?

Savitch's theorem "test[s] the existence of a path from a vertex s to another vertex t that uses at most ...
5
votes
2answers
108 views

Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

The question was asked in an interview, and I'm not sure if this is the most optimized answer, but here goes- You have an undirected acyclic graph, where each node has a non-negative value ...
0
votes
0answers
44 views

Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
1
vote
1answer
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 ...
0
votes
0answers
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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, ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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....
1
vote
1answer
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}$:- ...
1
vote
0answers
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. ...
0
votes
0answers
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 ...
1
vote
1answer
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. ...
3
votes
1answer
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 ...
3
votes
2answers
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 ...
2
votes
2answers
432 views

Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive: ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
73 views

Shortest tour visiting given set of nodes in knight tour graph

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$ (...
0
votes
0answers
19 views

algorithm that finds minimal vertex cover of a given vertex

i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to. not sure on how to do it correctly, ...

1
2 3 4 5
8