什么是必要做的DFS按递减顺序整理的Kosaraju算法时间寻找强连接组件的？ [英] What is the necessary of doing DFS in decreasing order of finishing times in Kosaraju algorithm for finding Strongly connected components?

问题描述

我学习Kosaraju算法从这里 Kosaraju寻找强连通分量算法。
但我不明白是什么做的DFS（G ^ T）递减顺序整理倍的必要性IE提到在上面的链接点3。

I am learning Kosaraju algorithm for finding strongly connected components from here Kosaraju algorithm .
But I can't understand what is the necessity of doing dfs(G^T) in decreasing order of finishing times i.e mentioned in Point 3 in above link.

推荐答案

考虑与两个顶点A和B以及从B到A（以G ^ T或A到B）一个边缘的简单图形。如果你做的顶点DFS（G ^ T），以A则B则输出这是一个强连通分量。而应该是两个独立的组件。

Consider a simple graph with two vertices A and B and one edge from B to A (or A to B in G^T). If you do dfs(G^T) on the vertices in order A then B then you output this as a single strongly connected component. Whereas it should be two separate components.

非正式的，做的顶点指定顺序的必要性，以确保您只去上下G链接第一个G ^ T链接时，你也可以去。

Informally, the necessity of doing the vertices in the specified order is to ensure you only go "up" G^T links when you can also go "down" G links first.

这篇关于什么是必要做的DFS按递减顺序整理的Kosaraju算法时间寻找强连接组件的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！