# Tag Info

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

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

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

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

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

### 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, ...
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 ...
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 ...
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 ...
1 vote
Accepted

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

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