Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

95 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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, ...
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 ...
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 ...
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, ...
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 ...
0
votes
0answers
105 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
18 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
0answers
30 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 ...
0
votes
0answers
24 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 ...
0
votes
0answers
70 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 ...
0
votes
0answers
20 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 ...
0
votes
0answers
37 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
71 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
522 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
49 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
68 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
0
votes
0answers
36 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
2answers
797 views

How to traverse a graph in reverse with dfs

So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, ...
0
votes
0answers
131 views

How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
0
votes
0answers
26 views

Finding a path between 2 points passing through N points

Given a graph/plane with N points each at a given coordinate how could I find a path between 2 points via N other points where each point is weighted on how likely it is to be passed through. ...
0
votes
1answer
340 views

Longest-Path Layering algorithm

NOTES: there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash. the code provide in this post is python3 on the premise that it ...
0
votes
0answers
40 views

The path with the highest sum of weights

Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from ...
0
votes
0answers
94 views

Multi agent graph traversal with edge discovery

Suppose we are given a set of agents (say $P_1 , \dotsc, P_M$), an undirected graph G(V,A) and a set of initial vertices on $G$ where each agent is located. Initially only the edges connected to these ...
0
votes
0answers
116 views

Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder

I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
0
votes
1answer
487 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
0
votes
1answer
281 views

How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
0
votes
0answers
203 views

Distance of a Graph node to a group of nodes?

Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity ...
0
votes
0answers
288 views

Efficient algorithm to find an vertex that is not an articulation vertex

This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201. Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion ...
0
votes
0answers
41 views

Finding continuous line consisted of points surrounding points of different color

I have a problem with creating an algorithm that would find continuous line consised of points of one color (say blue) that surrounds points of different color (say red). This problem occurs in "Dots"...
0
votes
0answers
343 views

What is the time and space complexity of unidirectional bfs and bidirectional bfs?

How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?
0
votes
0answers
569 views

Finding a path visiting most nodes in complete digraph with cost limit and positive or negative edge weights

I'm leaving out some specifics because this is a challenge problem and I don't want to be spoon-fed the answer, but I need a nudge in the right direction. I am given a complete digraph with the ...
0
votes
0answers
373 views

Making DFS more efficient

I was looking for non-recursive implementation of DFS algorithm. I found the following pseudocode on this page. ...
0
votes
0answers
35 views

How to choose the maximum vertices you can delete from set while atleast 1 of its neighbors is in set?

We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected: ...
0
votes
0answers
204 views

What is the algorithmic complexity of DFS under the cache oblivious model?

Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size &...
0
votes
0answers
669 views

Traveling Salesman problem solution for small graph?

So let's say i have a graph like this and salesman starts his journey at "A" How do i solve the TSP problem for this graph with pen and paper on exam?
0
votes
0answers
480 views

Fastest Algorithm to find shortest path between two edges in a graph

If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)? I am trying to answer a question in the EPI book. ...
0
votes
0answers
49 views

optimal path for traversing nodes

So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least ...
0
votes
0answers
618 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
0
votes
0answers
162 views

Generalized steps to find tree traversal for any m-ary tree

So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I ...
0
votes
0answers
525 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
0
votes
1answer
517 views

Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question. It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order ...
-1
votes
1answer
103 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 .
-1
votes
2answers
5k views

Minimum spanning tree using DFS and BFS

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs? I have gone through many answers but each answer says something different and I am not convinced....

1
2