Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
351
questions
0
votes
0answers
8 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
25 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
22 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
50 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
66 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
39 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
32 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
24 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
51 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
50 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
20 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
105 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 \...
0
votes
1answer
34 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
19 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
33 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
36 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
51 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
155 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
56 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
51 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
41 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 ...
1
vote
2answers
234 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
33 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
64 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
88 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
53 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
22 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
70 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
vote
0answers
248 views
About shortest cycles in undirected graphs
In an undirected (and unweighted) graph, to find the shortest cycle containing a specific vertex $s$, it is usually said to run a BFS from $s$ and the first time to find a re-visit, then that is the ...
0
votes
0answers
16 views
Is it possible to implement iterative pre/in/post-order traversal with only one stack?
All iterative algorithms I've seen for pre-order, in-order, and post-order traversals of trees have used two stacks. Is it possible to do it with one? I've been thinking about it for ever, I haven't ...
1
vote
1answer
220 views
Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node
For this I came up with a DFS recursion.
Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.
The element with ...
0
votes
0answers
86 views
Making graph acyclic by removing back edges in depth first and breadth traversal
I came across following points:
Removing all back edges produced by DFS makes the graph acyclic.
For a directed graph, the absence of back edges with respect to a BFS
tree implies that the graph is ...
0
votes
0answers
16 views
Comparing shortest path distance and relation between two modes present in FIFO queue at the same time during breadth first traversal
I came across following problem:
Consider two vertices $a$ and $b$ that are simultaneously on the FIFO queue at same point during the execution of breadth first search from $s$ in an undirected ...
0
votes
1answer
216 views
Dijkstra's algorithm - Finding additional paths with same weight but different edges
given a network with n stations. assuming the shortest between s,t was found using dijkstra's algorithm. let that path be denoted as $(a_1,a_2,...,a_k)$
assume that between the nodes s and t, there's ...
5
votes
2answers
79 views
Algorithm for finding “mean center” of unweighted graph
I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does ...
1
vote
2answers
226 views
Dijkstra and A* Algorithms: Why is A* faster?
I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster ...
0
votes
0answers
27 views
Finding the minimal path from S to T that visit all vertices
So I have a complete and directed graph with weights.
I wish to find the shortest path from S to T that visits all other vertices in the graph at least once.
Another important piece of information I ...
1
vote
0answers
17 views
How do programs like Apache Airflow/ Luigi determine shortest path and how does that relate to graph theory?
I am looking for a simple layman's term explanation on how do programs like Apache Airflow or Luigi (or any Task/ETL schedulers) determine the shortest path to complete a certain task and make it ...
