Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

100 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
327 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 ...
1
vote
0answers
77 views

Looking for name of siblings-first-depth-second traversal order

I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name. The requirements of the algorithm are: it visits the parent before the children. it visits ...
1
vote
0answers
96 views

Node-weighted CSP in Prim's algorithm?

I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix: $$ \left[ \begin{...
0
votes
1answer
20 views

Non-brute force algorithm for a Eulerian like path

I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one ...
0
votes
0answers
13 views

Finding time complexity of a depth first traversal algorithm with a depth limit to get all node traversals starting from the root node

What would be the time complexity of a depth-first traversal algorithm on a graph, that is simply trying to retrieve all nodes being visited from starting node up until a depth limit is reached (i.e. ...
0
votes
1answer
44 views

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have ...
0
votes
0answers
48 views

For every node of a tree, find the nearest ancestor node such that val[node] is coprime to val[ancestor]

Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note ...
0
votes
1answer
25 views

speed of preorder traversal

I want to know the speed of preorder traversal of an tree. I do not mean its order of magntude which we know is O(n). I want something like 27n operations where an operation is precisely defined. ...
0
votes
0answers
21 views

Why we take decreasing order of finishing times and NOT increasing order of discovery times in kosaraju algorithm?

We take decreasing order of finishing times in $G^t$ (transpose of Graph G) to know whther the path exists in other direction as shown below. But why can'nt WE take increasing order of discovery time ...
0
votes
0answers
62 views

Complexity of Finding Every Cycle in a Graph?

What's the best asymptotic complexity of finding every cycle in a simple, directed graph? I haven't been able to find anything regarding this online. I'm able to use DFS for cycle detection, but I'm ...
0
votes
0answers
32 views

Question regarding a particular type of graph

Let $G = (V,E)$ be a directed graph where every vertex is represented by an $n$ bit string. The edges are represented by two polynomial-sized circuits $S$ and $P$. There is an edge from $u$ to $v$ if ...
0
votes
0answers
45 views

Graph algorithm to group nodes by level and group size

I have a directed graph representing some topics organized as follows (below screenshot is a subset of the graph): I'm looking for an algorithm to group a set of nodes (in blue in the diagram) ...
0
votes
0answers
29 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
18 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 ...
0
votes
0answers
32 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 ...
0
votes
0answers
23 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 ...
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
121 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
32 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
58 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
78 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
37 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
111 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
85 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
2answers
1k 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
88 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
38 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
0answers
151 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
27 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
393 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
41 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
98 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
124 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
634 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
326 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
241 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
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
372 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
666 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
443 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
247 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
696 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
487 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
50 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
663 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
163 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
539 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
634 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
183 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
2