Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
2
votes
0answers
49 views

How to quickly determine whether a poset is a lattice?

Recently I encountered an interesting problem while studying discrete mathematics: Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the ...
-2
votes
0answers
16 views

how to represent a weighted graph using two different data structures&write an algorithm calculating the number of arcs For each of these structures [closed]

The figure below represents a graph G. The set of its vertices is {a, b, c, d, e, f, g}. The arcs are labeled by float numbers , as shown in the figure i represented this graph using adjacency matrix ...
0
votes
1answer
27 views

Can anyone explain how look-up tables are used for optimal Rubik's cube solvers such as Thistlethwaite's or Kociemba?

I have implemented Thistlethwaite's algorithm however, it is far too slow as it is only using graph traversal over many Rubik's cube states. I am currently unsure of how look-up tables are implemented ...
1
vote
2answers
84 views

Proving that a preorder traversal of a rooted tree can be performed in linear time

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
2
votes
0answers
39 views

Optimal Item Locations given Traversal Paths

I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations. Additionally, I have a ...
3
votes
2answers
1k views

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition): A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at ...
0
votes
1answer
34 views

Create Shortest Path tree for every node after Floyd Warshall in O(nm)

Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
1
vote
1answer
26 views

Longest path in a strongly connected component

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component. My idea is: In a strongly connected component ...
1
vote
2answers
233 views

Does DFS have better constants/complexity than Backtracking on a Graph?

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
0
votes
1answer
378 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
1answer
74 views

Each cycle in the graph, the edge with the minimum weight belongs to MST

Let $G=(V,E)$ be a weighted undirected connected graph and $w: E \to \mathbb{R^{+}}$ a weight function so that there are no two edges that have the same weight, and $T$ is an MST of $G$ . Then in ...
1
vote
0answers
34 views

What does “yields” mean in the phrase *yields no back edges* in DFS?

What does yields mean in the phrase yields no back edges in the context of DFS? ...
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
941 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 ...
1
vote
1answer
28 views

How does node expansion work in a graph for AI search?

I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city ...
0
votes
1answer
36 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 ...
1
vote
1answer
83 views

What does Dijkstra's algorithm become, when you replace path cost with edge cost?

Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are ...
1
vote
1answer
525 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 ...
1
vote
1answer
45 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, ...
3
votes
1answer
62 views

Trapezoidal decomposition of a graph

When we plan the motion of a robot we may apply the trapezoidal decomposition of free space. While applying the trapezoidal decomposition we add nodes to both the centers of trapezoids and vertical ...
3
votes
2answers
1k views

General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
0
votes
2answers
38 views

Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
1
vote
0answers
27 views

Simultaneous binary (n-ary) search

I have a balanced $k$-ary B-tree with $N$ leaves (where N is a power of $k$ for simplicity) and I need to simultaneously locate $\ell$ leaves in it. What is the expected number of nodes I will need to ...
6
votes
1answer
227 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
1
vote
1answer
56 views

Question about the conditions to find articulation points in a graph

I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph. In it, we first ...
1
vote
1answer
74 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
1answer
29 views

For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two ...
34
votes
9answers
50k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
9
votes
4answers
22k views

Why does DFS only yield tree and back edges on undirected, connected graphs?

Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge. Now, from intuition and in class lectures by Steven Skiena, I know ...
11
votes
1answer
3k views

Graphs that cause DFS and BFS to process nodes in the exact same order

For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-...
1
vote
1answer
210 views

Post numbers in DFS tree of an undirected graph

How could you prove: An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the ...
0
votes
1answer
22 views

Floyd Warshall with constraints

I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths ...
1
vote
1answer
62 views

Can the loops be in any order in the Floyd-Warshall algorithm?

I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page: ...
0
votes
0answers
43 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 ...
1
vote
0answers
18 views

Greedy Best-First Search Performance for Tree and Graph Space

I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being not optimal in Tree Search for Finite and Infinite Spaces that it is ...
4
votes
1answer
89 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
1answer
19 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. ...
6
votes
1answer
1k views

A variant of travel salesman problem in grid graph

In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. ...
0
votes
1answer
307 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
1answer
595 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 ...
1
vote
1answer
10 views

Circular path visiting fewest nodes

I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good ...
0
votes
2answers
1k 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, ...
2
votes
3answers
504 views

Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?

I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
0
votes
1answer
35 views

How can I examine the subnetworks of a nearly fully connected graph?

I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a ...
0
votes
0answers
18 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 ...
2
votes
0answers
33 views

Counting paths by their type

An edge-labelled directed graph is the data of $G = (V, E, l)$ where $(V, E)$ is a directed graph, and $l \colon E \to \mathbb{P}$ is some function. (For the graph I am considering, labels take values ...
0
votes
0answers
43 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
41 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) ...
1
vote
1answer
145 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 ...

1
2 3 4 5
8