0
$\begingroup$

"Introduction to algorithms" also known as CLRS, proves the correctness of the algorithm to compute the Strongly Connected Components in two ways, one of which is

Here is another way to look at how the second depth-first search operates. Consider the component graph $(G^T)^{SCC}$ of $G^T$. If we map each strongly connected component visited in the second depth-first search to a vertex of $(G^T)^{SCC}$, the second depth-first search visits vertices of $(G^T)^{SCC}$ in the reverse of a topologically sorted order. If we reverse the edges of $(G^T)^{SCC}$, we get the graph $((G^T)^{SCC})^T$. Because $((G^T)^{SCC})^T = G^{SCC}$, the second depth-first search visits the vertices of $G^{SCC}$in topologically sorted order.

The algorithm is:

  1. Execute DFS on $G$ (starting at an arbitrary starting vertex), keeping track of the finishing times of all vertices.
  2. Compute the transpose,
  3. Execute DFS on $G^T$, starting at the vertex with the latest finishing time, forming a tree rooted at that vertex. Once a tree is completed, move on to the unvisited vertex with the next latest finishing time and form another tree using DFS and repeat until all the vertices in $G^T$ are visited.
  4. Output the vertices in each tree formed by the second DFS as a separate strongly connected component.

Might I ask you what the quoted block of text mean? Thank you in advance.

$\endgroup$
4
  • 1
    $\begingroup$ what part in the quotes, you did not understand? Did you try with some examples? $\endgroup$ Dec 20 '21 at 16:14
  • $\begingroup$ Honestly? I understood nothing XD $\endgroup$ Dec 20 '21 at 18:03
  • 1
    $\begingroup$ I'm afraid "please explain this paragraph to me" is not a good fit for this format, as it's unclear what you did understand and didn't understand; it might be asking too much; and I'm concerned if someone explained in different language you might just say you didn't understand that, either. This is a question-and-answer site, and it is designed for specific, narrowly focused questions. So asking a specific question about that section of text might be appropriate, but just asking someone to explain the whole thing isn't. As suggested, trying some examples is often a good way to understand. $\endgroup$
    – D.W.
    Dec 20 '21 at 20:24
  • $\begingroup$ @inuyasha-yagami I am sorry. So, What does "mapping each strongly connected component visited in the second depth-first search to a vertex of $(G^T)^{SCC}$ mean? Thank you very much. $\endgroup$ Dec 20 '21 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.