Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
309
questions
2
votes
0answers
16 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 ...
0
votes
2answers
46 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 ...
-2
votes
0answers
12 views
Given a preorder traversal and postorder traversal of a binary tree, is it always possible to find the corresponding Inorder
For instance,
given preorder : F , A , B , C , D , E , G , H , I
given postorder: A , C , E , D , B , H , I , G , F
I am not able to proceed after the sequence -...
0
votes
0answers
22 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
129 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
25 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
274 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
115 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
25 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
25 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
40 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
21 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
74 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
61 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
55 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
23 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
42 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:
...
2
votes
1answer
50 views
Arranging Colors in a Grid; Two Dimensional TSP?
I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6x8 on which I am attempting to arrange 48 color swatches, such that the transition from each swatch to ...
2
votes
1answer
56 views
Efficiently compute the sum of edge weights product of all possible path in a DAG
I thought of using Depth First Search (DFS) to find all possible paths in O(|V|+|E|). However, computing the product of all the edge weights for a path is O(2^N). Is there any way to compute this more ...
0
votes
1answer
64 views
binomial tree number of nodes
Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .
2
votes
1answer
47 views
How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?
I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List ...
1
vote
2answers
44 views
Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find ...
0
votes
0answers
19 views
Detecting whether a node belong to a cutset with the least memory consumption as possible
I'm working on a problem about connected components implemented by cutsets.
Given a cutset, I want to determine whether some node lies within the connected component created by such cutset. The most ...
4
votes
2answers
210 views
How to evaluate all possible groups of adjacent tiles in 2D array?
I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain ...
1
vote
1answer
57 views
Directed graph reachability
Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?
0
votes
1answer
31 views
Strongly connected graph proof
Here I have a proof related to strongly connected graph from Algorithms book.
However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof.
According ...
0
votes
0answers
24 views
Why is BFS “vertex based” and DFS “edge based”?
I am trying to understand the various differences between Breadth-first and Depth-first search on graphs. Two sources state that BFS is "vertex based" and DFS is "edge based" even though in ...
0
votes
0answers
62 views
Verifying the minimum cost from each node to a sink node in linear time
Problem Statement:
Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for ...
0
votes
1answer
190 views
how to prove correctness of this BFS algorithm?
Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that ...
0
votes
0answers
33 views
Two algorithms for finding bridges in a graph that are almost the same
So I'm looking at an algorithm for finding bridges in an undirected graph. The thing is, there is a version of this algorithm that I've used so far that looks like this (C++)
...
0
votes
0answers
122 views
Maximum space consumption of stack and queue for DFS and BFS
I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS.
Since BFS and DFS while traveling graphs have ...
0
votes
0answers
34 views
What is the approximation for odd cycle transversal?
What is the best approximation for odd cycle transversal? (on general graphs)
Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels
2
votes
2answers
103 views
For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Traditionally, the traveling salesman problem has you visit a city at least once and at most once.
However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1
vote
2answers
59 views
Verifying connectivity of a graph in O(n^2)
I trying to solve the following problem in $O(n^2)$:
We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to
make the graph ...
2
votes
0answers
47 views
Similar-path shortest paths
Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
2
votes
1answer
50 views
is it always true that the depth of BFS is $\leq$ DFS?
I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS?
From what I understand, the tricky part here is the ...
2
votes
1answer
81 views
How to merge a lot of trees into one single graph?
I have a few different trees, which resemble what the AST that compilers often deal with.
For example:
tree 1
( (a, b), (c, d) )
Imagine that each tree split represents the function "add", then ...
11
votes
4answers
4k views
Can the pre-order traversal of two different trees be the same even though they are different?
This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.
It is also mentioned that the in-order ...
2
votes
1answer
29 views
Minimize sequence storage by overlapping prefixes
I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can ...
3
votes
1answer
116 views
Cannibals missionaries problem - solving usings graphs
I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other ...
3
votes
2answers
71 views
Minimize number of DFS searches in a graph
I got a weird homework question about graph.
A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed ...
1
vote
0answers
157 views
Maximum size of BFS open set on a grid
I have a 2D grid of infinite size that can either be 4-connected or 8-connected (as defined in https://en.wikipedia.org/wiki/Pixel_connectivity). I am implementing breadth-first search on this grid ...
2
votes
1answer
118 views
Subtree with minimum sum of nodes' costs
Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that ...
1
vote
1answer
269 views
Define the time complexity of Kruskal's algorithm as function
I am trying to define the time complexity of Kruskal's algorithm as function dependant on:
the number of vertices V
the number of edges ...
0
votes
0answers
34 views
Are these algorithms for detecting cycles in directional graph correct?
I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not ...
0
votes
1answer
49 views
Is a subgraph of G always connected
I am trying to figure out if given a connect graph with N nodes and A edges, its subgraphs are connected.
In order word: given a graph G, can I have a subgraph of G that is not connected?
Or: can a ...
0
votes
1answer
41 views
Idea for a Graph Based Algorithm
Assume there is a Shopping Mall x and all the roads in the city are one way such that, irrespective of the path you take starting from x, you will always end up at vertex x. Device an algorithm to ...
3
votes
2answers
88 views
Fewest traversals to visit all vertices of DAG
I want to find the fewest traversals to visit all vertices of a DAG. To take a very simple case:
...
0
votes
0answers
57 views
Whats the time complexity of Prims Algo. without heaps (using priority queue)?
Here's my attempt:
Initialisation -
...
