Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
4
votes
1answer
61 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 ...
1
vote
0answers
41 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
33 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
18 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
30 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
43 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
111 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? ...
0
votes
1answer
29 views

Is the subgraph of a mst an mst of the subgraph that its vertices represent

Let $G$ be a connected weighted undirected graph. Let $T$ be a mst of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$ contains the vertex $a$...
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
54 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
40 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
135 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
62 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
83 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
21 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
70 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
18 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
161 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
188 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
61 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 ...
0
votes
0answers
15 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
105 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
66 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
181 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 ...
0
votes
1answer
137 views

Why is my algorithm version so slow with this input?

Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (...
1
vote
1answer
78 views

Breadth First Traversal for graph with multiple connected components

I read BFS and DFS from CLRS and realized that the BFS algorithm does not consider graph with multiple connected components but only with single connected component, whereas DFS algorithm considers ...
2
votes
1answer
284 views

O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list: Initialize an array of integers "colors" with V elements being 1 Using ...
4
votes
2answers
694 views

Find all nodes on simple paths between two nodes in cyclic directed graph

Given two nodes U and V in a cyclic directed graph, how can I find the set of nodes that are part of a simple path from ...
1
vote
0answers
37 views

Finding all non-comparable nodes in DAG

I have a DAG and I want to list all pairs of vertices that are not comparable (there is no path from the first to the second or the second to the first). In this image (taken from this StackOverflow ...
1
vote
0answers
46 views

Find all Eulerian cycles in a directed graph

I am trying to create an algorithm that can find all Eulerian cycles in a directed graph. I was able to make an algorithm that can find one cycle in the graph, but I don't know how to find all the ...
0
votes
2answers
123 views

Graph theory: BFS (Breadth First Search) - why is current processed first?

I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn't "breadth first" mean "Process children first, ...
0
votes
0answers
23 views

Is there a Weisfeiler-lehman kernel for directed, labelled and with cycles graphs?

I have a set of labelled, directed and cyclic graphs and a I need to perform a supervised learning algorithm in this data. I have found a single paper A Persistent Weisfeiler-Lehman Procedure for ...
5
votes
0answers
84 views

Find the 'best' longest common subsequence

I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
-1
votes
1answer
93 views

Is there an example of when DFS will not return the min. spanning tree?

If we have a connected, weighted, undirected graph. Can anyone provide an example where DFS will not return the MST? No matter what vertex we start from ?
4
votes
1answer
75 views

Computing a pre-topological sort using a BFS/a queue

Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes ...
0
votes
0answers
61 views

BFS vs DFS, and Timing of Marking Vertex as Visited

The Wikipedia article on Depth-Frist Search states that: The non-recursive implementation is similar to breadth-first search but differs from it in two ways: it uses a stack instead of a ...
2
votes
1answer
44 views

An algorithm for topological sorting based on depth-first search: why do we need two tags?

Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows: ...

1
2 3 4 5
7