5 votes
Accepted

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

The MST of $G$ is not well-defined since there might be multiple MSTs of a graph. However, it can be shown that: Claim 1: either all MSTs use only edges with integer weights or none of them does. ...
user avatar
  • 23.9k
4 votes
Accepted

What is the relation between Topological Sort and Strongly Connected Components?

One connection could be the following: Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge ...
user avatar
  • 10.9k
4 votes

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

A simple algorithm Here is the simplest and fastest algorithm to determine the MST of $G$ only uses edges with an integer weight. It runs in $O(E\,\alpha(V))=O(n\,\alpha(n))$ time. Define weight ...
user avatar
  • 34.7k
3 votes
Accepted

Maximum Independent Set of special Directed Graph

The type of graph you are describing is identical to the one encountered in Pollard's rho algorithm. Connected components of your graph are cycles with directed trees feeding into them (possibly none)....
user avatar
2 votes

Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

Assume the graph is a directed acyclic graph throughout. The algorithm is correct In the first recursion, the algorithm finds a node $u$ that has no incoming edges. In the second recursion, the ...
user avatar
  • 34.7k
2 votes

What is the correct complexity of All paths from Source to Target DFS solution?

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots ...
user avatar
  • 101
2 votes
Accepted

Iterative Depth First Search for cycle detection on directed graphs

Using the same logic as the recursive algorithm, I added on the stack a pos value which keeps track of the position of the last descendant currently processing. ...
user avatar
  • 41
2 votes

First-time and second-time seen edges in DFS on undirected graphs

Here is the simplest example. Let the graph contain two vertices, $x$ and $y$ with one edge $\{x,y\}$. Here is a run of the algorithm. $x$ and $y$ are marked as "undiscovered". $y$ is ...
user avatar
  • 34.7k
2 votes

What's the name of this DFS variation

This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function w. This strategy uses a priority queue (e....
user avatar
  • 362
2 votes
Accepted

pictorial representation of pre and post ordering for edge types

"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible. The right assumption ...
user avatar
  • 34.7k
2 votes

Find palindrome in directed Graph where edges are either blue or red

Here's a possible algorithm. Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, ...
user avatar
  • 12.4k
2 votes
Accepted

Connectivity in Directed Graph

The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references ...
user avatar
2 votes
Accepted

In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest

Yes use induction. You will assume that $G_\pi$ is a forest, and you want to prove that $G_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm. The key point, is that a ...
user avatar
  • 10.9k
2 votes
Accepted

For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees

Consider the following graph: A possible DFS starting from $a$ visits the vertices in this order: $\langle a, b, c, d \rangle$ producing the cross-edge $(c,b)$. A possible DFS starting from $b$ ...
user avatar
  • 23.9k
2 votes
Accepted

Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?

First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs. Now graphs can be directed, which would correspond to having a labyrinth with ...
user avatar
  • 23.9k
2 votes

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

Here is one way to do it. First get all the integer edges $E_{\mathbb{Z}}=\{e_1, ..., e_k\}$ in $O(m)=O(n)$ time. Since their weights are integers and bounded by $O(n)$, you can use bucket sort/radix ...
user avatar
2 votes

Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book

I'm not sure what the problem is, but I will still try to answer. The predecessor of $v$ in a path from $u$ to $v$ is the last vertex seen before $v$. Since there exists a path from $u$ to $v$ then, ...
user avatar
  • 7,193
1 vote

Minimum steps needed to partially cover a sequence of points on a grid

There is a straightforward dynamic programming algorithm. You only need to know, for each $i,j$, the length of the shortest path to $(x_i,y_j)$ that covers the first $i$ points, and the length of the ...
user avatar
  • 143k
1 vote

Transforming from neighbour representation to grid representation

Pick an arbitrary node. Assign it the coordinates $(0,0)$. Now run any graph traversal algorithm -- say, depth-first search. When you visit a node, you know its coordinates. Now you can look at ...
user avatar
  • 143k
1 vote
Accepted

Print all nodes which are the endpoint of the diameter of a tree

One-line takeaway: a tree has either one center or two adjacent centers, which are shared by all diameters. The clue to solve the problem faster is sort of hidden in the symmetric tree given in the ...
user avatar
  • 34.7k
1 vote
Accepted

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

Compute all pair to pair distances $D[u,v]$ for $u,v \in V$ using Floyd-Warshall. For each vertex $s \in V$ construct a graph $H_s$ as follows: For each edge $e = (u,v)$ check whether $D[s,u] + D[u,v]...
user avatar
  • 23.9k
1 vote

Is DFS better than BFS for space complexity when finding path from root to a node in a tree?

To keep it short and simple, the answer is yes. BFS, in addition to the set of visited nodes, makes use of queue for unprocessed ...
user avatar
1 vote

Is DFS better than BFS for space complexity when finding path from root to a node in a tree?

In the case of the binary tree, and assuming your binary tree is balanced, yes, I think you will be using more space at any given time in general with BFS. DFS would be allocating and releasing memory ...
user avatar
1 vote

Check if two graphs are edge-disjoint

The adjacency matrix $A_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A_G$ is a $V \times V$ matrix, $A_G(v,v) = 0$ for all $v \in V$, and $A_G(u,v) = 1$ if $\{u,v\} \in E$ and $A_G(u,v) ...
user avatar
1 vote
Accepted

DFS produces the correct Topologically ordered sequence

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph. Now to prove that the ...
user avatar
  • 275
1 vote
Accepted

find the strong component containing the vertex v

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the ...
user avatar
  • 7,193
1 vote

Alternatives for finding sources in a DAG

Use a priority queue to keep a list of all vertices with prioritization on in-degrees. Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$. Repeat ...
user avatar
  • 13.3k
1 vote
Accepted

Question about the conditions to find articulation points in a graph

Here is the proof: Given we have A -> B as an edge where A is not the root, let's assume A is an articulation point thats not the root. Removing it results in 2 ...
user avatar
  • 227
1 vote

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

When you explore a graph of $N$ vertices and $E$ edges, you basically need to store the visited vertices in a $N$ boolean array. But eventually (when you are interested in retrieving path and not only ...
user avatar
  • 1,730

Only top scored, non community-wiki answers of a minimum length are eligible