# 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
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 ...
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 ...
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{...
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 ...
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. ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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) ...
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$. ...
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 ...
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 ...
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 ...
44 views

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 ...