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.
...
- 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 ...
- 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 ...
- 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)....
- 270k
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 ...
- 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 ...
- 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.
...
- 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 ...
- 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....
- 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 ...
- 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, ...
- 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 ...
- 3,976
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 ...
- 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$ ...
- 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 ...
- 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 ...
- 503
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, ...
- 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 ...
D.W.♦
- 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 ...
D.W.♦
- 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 ...
- 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]...
- 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 ...
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 ...
- 31
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) ...
- 270k
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 1,730
Only top scored, non community-wiki answers of a minimum length are eligible