软件
軟件
연건
SOFT WARE
2014年
3期
72-75
,共4页
DAG%Tarjan%Kosaraju%Gabow时间复杂度
DAG%Tarjan%Kosaraju%Gabow時間複雜度
DAG%Tarjan%Kosaraju%Gabow시간복잡도
DAG%Tarjan%Kosaraju%Gabow Time Complexity
有向图的强连通分量应用非常广泛，比如有向图的强连通分量数量巨大的时候，为了更加高效必须要用缩点法。深度优先遍历是求有向图的强连通分量的一个有效方法，根据实现方式的不同，总体上，求有向图的强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法。三种算法的时间复杂度均为O(n+e)(n为顶点数，e为边数)。
有嚮圖的彊連通分量應用非常廣汎，比如有嚮圖的彊連通分量數量巨大的時候，為瞭更加高效必鬚要用縮點法。深度優先遍歷是求有嚮圖的彊連通分量的一箇有效方法，根據實現方式的不同，總體上，求有嚮圖的彊連通分量有三種算法，分彆是Kosaraju算法，Gabow算法和Tarjan算法。三種算法的時間複雜度均為O(n+e)(n為頂點數，e為邊數)。
유향도적강련통분량응용비상엄범，비여유향도적강련통분량수량거대적시후，위료경가고효필수요용축점법。심도우선편력시구유향도적강련통분량적일개유효방법，근거실현방식적불동，총체상，구유향도적강련통분량유삼충산법，분별시Kosaraju산법，Gabow산법화Tarjan산법。삼충산법적시간복잡도균위O(n+e)(n위정점수，e위변수)。
The application of SCC is normal.For example,when the number of SCC is giant,in order to improve the efficiency ,it must use the way of reducing the vertexs.The DFS is an effective way.According to the way of accomplishing,in general,there are three algorithms what can find the SCC of digraph including Kosaraju,Tarjan,Gabow.The Time Complexity of each is O(n+e).
