寻找强连通分量？ [英] Finding Strongly Connected Components?

问题描述

我的书定义了一个方法来找到线性时间有向图的强连通分量。除了几个其它算法找到强连通分量（即的Tarjan的算法）也能找到的组件中线性时间

My book defines a method to find the strongly connected components of a directed graph in linear time. In addition several other algorithms to find strongly connected components (i.e. Tarjan's algorithm) is also able to find the components in linear time.

然而，所有这些算法所需要的图形在减少的发布的值（时间的顶点左）被命令的顶点。常见的排序算法，如采取归并为O（n log n）的时间。

However all of these algorithms require the vertices of the graph to be ordered in decreasing post values (time the vertex is left). Common ordering algorithms such as Mergesort take O(n log n) time.

因此，如何做这些算法设法完成定位的线性时间的强连接组件，如果订购顶点通过列表的发布的值需要为O（n log n）的时间？

Therefore how do these algorithms manage to complete locating the strongly connected components in linear time, if ordering the list of vertices by post values takes O(n log n) time?

推荐答案

由于时间（由后值的测量的那种）是单调非降作为时间（由深度 - 执行的步骤的数目的函数第一搜索程序），就足够了立即追加每个节点列表遍历离开它之后。在遍历的最后，该列表是按排序顺序

Since "time" (the kind by which the post values are measured) is monotonically nondecreasing as a function of time (the number of steps executed by the depth-first search program), it suffices to append each node to a list immediately after the traversal leaves it. At the end of the traversal, the list is in sorted order.

另外，由于提交值是整数上界多项式，在某些机型可以使用例如对它们进行排序的线性时间基数排序。

Alternatively, since the post values are integers bounded above polynomially, on some machine models it is possible to sort them in linear time using e.g. radix sort.

这篇关于寻找强连通分量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！