如果所有顶点对之间都有一条路径，则有向图是强连通的。强连通组件( 鳞状细胞癌 )有向图的子图是极大强连通子图。例如，下图中有3个SCC。
null
我们讨论过 强连通分量的Kosaraju算法 .前面讨论的算法需要对一个图进行两次DFS遍历。在这篇帖子里， 塔扬算法 讨论了只需要一次DFS遍历的。
Tarjan算法基于以下事实： 1.DFS搜索生成DFS树/林 2.强连接组件构成DFS树的子树。 3.如果我们可以找到这些子树的头，我们可以打印/存储该子树中的所有节点（包括头），这将是一个SCC。 4.从一个SCC到另一个SCC没有后边（可以有交叉边，但在处理图形时不会使用交叉边）。
为了找到SCC的头部，我们计算了磁盘和低位阵列（如 关节点 , 桥 , 双连通元件 )如前几篇文章所述，low[u]表示最早访问的顶点（发现时间最短的顶点），可以从以u为根的子树到达。如果disc[u]=low[u]，则节点u为头。
下图是该方法的说明：
![图片[2]-Tarjan寻找强连通分量的算法-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20190702/geeks_TarjansAlgorithms.png)
强连通分量只与有向图有关，而Disc和Low值与有向图和无向图都有关，所以在上图中我们采用了无向图。 在上图中，我们展示了一个图及其DFS树（根据边的遍历顺序，同一个图上可能有不同的DFS树）。
在DFS树中，连续箭头是树边，虚线箭头是后边( DFS树边 图中显示了每个节点的Disc和Low值（Disc/Low）。
光盘： 这是节点被访问的时间1 圣 穿越时的时间。对于节点A、B、C。。，J在DFS树中，Disc值为1、2、3、。。，10 低： 在DFS树中，树的边缘引导我们向前，从祖先节点到它的一个后代。例如，从节点C，树边可以带我们到节点G、节点I等。后边带我们向后，从一个后代节点到它的一个祖先节点。例如，从节点G开始，后边将我们带到E或C。如果我们同时查看树和后边，那么我们可以看到，如果我们从一个节点开始遍历，我们可能会通过树边向下遍历树，然后通过后边向上遍历。例如，从节点E，我们可以下降到G，然后上升到C。类似地，从E，我们可以下降到I或J，然后上升到F。节点的“低”值通过该节点的子树告诉最顶端的可到达祖先（具有最小可能的圆盘值）。因此，对于任何节点，低值都等于其Disc值（节点是其自身的祖先）。然后我们查看它的子树，看看是否有任何节点可以将我们带到它的任何祖先。如果子树中有多条后缘将我们带到不同的祖先，那么我们将选择具有最小圆盘值的后缘（即最上面的后缘）。如果我们看节点F，它有两个子树。带有节点G的子树将我们带到E和C。另一个子树只将我们带回到F。这里最上面的祖先是C，F可以到达，所以F的低值是3（C的圆盘值）。
基于以上讨论，应该清楚的是，B、C和D的低值为1（因为A是B、C和D可以到达的最高节点）。同样，E、F、G的低值为3，H、I、J的低值为6。 对于任何节点u，当DFS启动时，Low将被设置为其Disc 1 圣 .
随后，将逐个对其每个子级v执行DFS，低值u可以在两种情况下更改： 案例1（树边）： 如果尚未访问节点v，则在完成节点v的DFS后，将低[u]和低[v]的最小值更新为低[u]。 低[u]=min（低[u]，低[v]）； 案例2（后缘）： 当已经访问了子v时，最低的low[u]和Disc[v]将更新为low[u]。 低[u]=最小值（低[u]，圆盘[v]）；
在第二种情况下， 我们能用低电压代替圆盘电压吗？？ 答案是 不 .如果你能想一想为什么答案是 不 ，您可能理解了低音和光碟的概念。
相同的Low和Disc值有助于解决其他图形问题，如 关节点 , 桥 和 双连通元件 . 为了跟踪在头部扎根的子树，我们可以使用堆栈（在访问时继续推节点）。找到头部节点后，从堆栈中弹出所有节点，直到将头部从堆栈中取出。
为了确保，我们不考虑交叉边，当我们到达一个已经访问过的节点时，我们只需要处理访问的节点，如果它存在于堆栈中，否则忽略节点。
下面是Tarjan打印所有SCC的算法的实现。
C++
// A C++ program to find strongly connected components in a given // directed graph using Tarjan's algorithm (single DFS) #include<iostream> #include <list> #include <stack> #define NIL -1 using namespace std; // A class that represents an directed graph class Graph { int V; // No. of vertices list< int > *adj; // A dynamic array of adjacency lists // A Recursive DFS based function used by SCC() void SCCUtil( int u, int disc[], int low[], stack< int > *st, bool stackMember[]); public : Graph( int V); // Constructor void addEdge( int v, int w); // function to add an edge to graph void SCC(); // prints strongly connected components }; Graph::Graph( int V) { this ->V = V; adj = new list< int >[V]; } void Graph::addEdge( int v, int w) { adj[v].push_back(w); } // A recursive function that finds and prints strongly connected // components using DFS traversal // u --> The vertex to be visited next // disc[] --> Stores discovery times of visited vertices // low[] -- >> earliest visited vertex (the vertex with minimum // discovery time) that can be reached from subtree // rooted with current vertex // *st -- >> To store all the connected ancestors (could be part // of SCC) // stackMember[] --> bit/index array for faster check whether // a node is in stack void Graph::SCCUtil( int u, int disc[], int low[], stack< int > *st, bool stackMember[]) { // A static variable is used for simplicity, we can avoid use // of static variable by passing a pointer. static int time = 0; // Initialize discovery time and low value disc[u] = low[u] = ++ time ; st->push(u); stackMember[u] = true ; // Go through all vertices adjacent to this list< int >::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of 'u' // If v is not visited yet, then recur for it if (disc[v] == -1) { SCCUtil(v, disc, low, st, stackMember); // Check if the subtree rooted with 'v' has a // connection to one of the ancestors of 'u' // Case 1 (per above discussion on Disc and Low value) low[u] = min(low[u], low[v]); } // Update low value of 'u' only of 'v' is still in stack // (i.e. it's a back edge, not cross edge). // Case 2 (per above discussion on Disc and Low value) else if (stackMember[v] == true ) low[u] = min(low[u], disc[v]); } // head node found, pop the stack and print an SCC int w = 0; // To store stack extracted vertices if (low[u] == disc[u]) { while (st->top() != u) { w = ( int ) st->top(); cout << w << " " ; stackMember[w] = false ; st->pop(); } w = ( int ) st->top(); cout << w << "" ; stackMember[w] = false ; st->pop(); } } // The function to do DFS traversal. It uses SCCUtil() void Graph::SCC() { int *disc = new int [V]; int *low = new int [V]; bool *stackMember = new bool [V]; stack< int > *st = new stack< int >(); // Initialize disc and low, and stackMember arrays for ( int i = 0; i < V; i++) { disc[i] = NIL; low[i] = NIL; stackMember[i] = false ; } // Call the recursive helper function to find strongly // connected components in DFS tree with vertex 'i' for ( int i = 0; i < V; i++) if (disc[i] == NIL) SCCUtil(i, disc, low, st, stackMember); } // Driver program to test above function int main() { cout << "SCCs in first graph " ; Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.SCC(); cout << "SCCs in second graph " ; Graph g2(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.SCC(); cout << "SCCs in third graph " ; Graph g3(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.SCC(); cout << "SCCs in fourth graph " ; Graph g4(11); g4.addEdge(0,1);g4.addEdge(0,3); g4.addEdge(1,2);g4.addEdge(1,4); g4.addEdge(2,0);g4.addEdge(2,6); g4.addEdge(3,2); g4.addEdge(4,5);g4.addEdge(4,6); g4.addEdge(5,6);g4.addEdge(5,7);g4.addEdge(5,8);g4.addEdge(5,9); g4.addEdge(6,4); g4.addEdge(7,9); g4.addEdge(8,9); g4.addEdge(9,8); g4.SCC(); cout << "SCCs in fifth graph " ; Graph g5(5); g5.addEdge(0,1); g5.addEdge(1,2); g5.addEdge(2,3); g5.addEdge(2,4); g5.addEdge(3,0); g5.addEdge(4,2); g5.SCC(); return 0; } |
JAVA
// Java program to find strongly connected // components in a given directed graph // using Tarjan's algorithm (single DFS) import java.io.*; import java.util.*; // This class represents a directed graph // using adjacency list representation class Graph{ // No. of vertices private int V; //Adjacency Lists private LinkedList<Integer> adj[]; private int Time; // Constructor @SuppressWarnings ( "unchecked" ) Graph( int v) { V = v; adj = new LinkedList[v]; for ( int i = 0 ; i < v; ++i) adj[i] = new LinkedList(); Time = 0 ; } // Function to add an edge into the graph void addEdge( int v, int w) { adj[v].add(w); } // A recursive function that finds and prints strongly // connected components using DFS traversal // u --> The vertex to be visited next // disc[] --> Stores discovery times of visited vertices // low[] -- >> earliest visited vertex (the vertex with // minimum discovery time) that can be reached // from subtree rooted with current vertex // st -- >> To store all the connected ancestors (could be part // of SCC) // stackMember[] --> bit/index array for faster check // whether a node is in stack void SCCUtil( int u, int low[], int disc[], boolean stackMember[], Stack<Integer> st) { // Initialize discovery time and low value disc[u] = Time; low[u] = Time; Time += 1 ; stackMember[u] = true ; st.push(u); int n; // Go through all vertices adjacent to this Iterator<Integer> i = adj[u].iterator(); while (i.hasNext()) { n = i.next(); if (disc[n] == - 1 ) { SCCUtil(n, low, disc, stackMember, st); // Check if the subtree rooted with v // has a connection to one of the // ancestors of u // Case 1 (per above discussion on // Disc and Low value) low[u] = Math.min(low[u], low[n]); } else if (stackMember[n] == true ) { // Update low value of 'u' only if 'v' is // still in stack (i.e. it's a back edge, // not cross edge). // Case 2 (per above discussion on Disc // and Low value) low[u] = Math.min(low[u], disc[n]); } } // head node found, pop the stack and print an SCC // To store stack extracted vertices int w = - 1 ; if (low[u] == disc[u]) { while (w != u) { w = ( int )st.pop(); System.out.print(w + " " ); stackMember[w] = false ; } System.out.println(); } } // The function to do DFS traversal. // It uses SCCUtil() void SCC() { // Mark all the vertices as not visited // and Initialize parent and visited, // and ap(articulation point) arrays int disc[] = new int [V]; int low[] = new int [V]; for ( int i = 0 ;i < V; i++) { disc[i] = - 1 ; low[i] = - 1 ; } boolean stackMember[] = new boolean [V]; Stack<Integer> st = new Stack<Integer>(); // Call the recursive helper function // to find articulation points // in DFS tree rooted with vertex 'i' for ( int i = 0 ; i < V; i++) { if (disc[i] == - 1 ) SCCUtil(i, low, disc, stackMember, st); } } // Driver code public static void main(String args[]) { // Create a graph given in the above diagram Graph g1 = new Graph( 5 ); g1.addEdge( 1 , 0 ); g1.addEdge( 0 , 2 ); g1.addEdge( 2 , 1 ); g1.addEdge( 0 , 3 ); g1.addEdge( 3 , 4 ); System.out.println( "SSC in first graph " ); g1.SCC(); Graph g2 = new Graph( 4 ); g2.addEdge( 0 , 1 ); g2.addEdge( 1 , 2 ); g2.addEdge( 2 , 3 ); System.out.println( "SSC in second graph " ); g2.SCC(); Graph g3 = new Graph( 7 ); g3.addEdge( 0 , 1 ); g3.addEdge( 1 , 2 ); g3.addEdge( 2 , 0 ); g3.addEdge( 1 , 3 ); g3.addEdge( 1 , 4 ); g3.addEdge( 1 , 6 ); g3.addEdge( 3 , 5 ); g3.addEdge( 4 , 5 ); System.out.println( "SSC in third graph " ); g3.SCC(); Graph g4 = new Graph( 11 ); g4.addEdge( 0 , 1 ); g4.addEdge( 0 , 3 ); g4.addEdge( 1 , 2 ); g4.addEdge( 1 , 4 ); g4.addEdge( 2 , 0 ); g4.addEdge( 2 , 6 ); g4.addEdge( 3 , 2 ); g4.addEdge( 4 , 5 ); g4.addEdge( 4 , 6 ); g4.addEdge( 5 , 6 ); g4.addEdge( 5 , 7 ); g4.addEdge( 5 , 8 ); g4.addEdge( 5 , 9 ); g4.addEdge( 6 , 4 ); g4.addEdge( 7 , 9 ); g4.addEdge( 8 , 9 ); g4.addEdge( 9 , 8 ); System.out.println( "SSC in fourth graph " ); g4.SCC(); Graph g5 = new Graph ( 5 ); g5.addEdge( 0 , 1 ); g5.addEdge( 1 , 2 ); g5.addEdge( 2 , 3 ); g5.addEdge( 2 , 4 ); g5.addEdge( 3 , 0 ); g5.addEdge( 4 , 2 ); System.out.println( "SSC in fifth graph " ); g5.SCC(); } } // This code is contributed by // Prateek Gupta (@prateekgupta10) |
Python3
# Python program to find strongly connected components in a given # directed graph using Tarjan's algorithm (single DFS) #Complexity : O(V+E) from collections import defaultdict #This class represents an directed graph # using adjacency list representation class Graph: def __init__( self ,vertices): #No. of vertices self .V = vertices # default dictionary to store graph self .graph = defaultdict( list ) self .Time = 0 # function to add an edge to graph def addEdge( self ,u,v): self .graph[u].append(v) '''A recursive function that find finds and prints strongly connected components using DFS traversal u --> The vertex to be visited next disc[] --> Stores discovery times of visited vertices low[] -- >> earliest visited vertex (the vertex with minimum discovery time) that can be reached from subtree rooted with current vertex st -- >> To store all the connected ancestors (could be part of SCC) stackMember[] --> bit/index array for faster check whether a node is in stack ''' def SCCUtil( self ,u, low, disc, stackMember, st): # Initialize discovery time and low value disc[u] = self .Time low[u] = self .Time self .Time + = 1 stackMember[u] = True st.append(u) # Go through all vertices adjacent to this for v in self .graph[u]: # If v is not visited yet, then recur for it if disc[v] = = - 1 : self .SCCUtil(v, low, disc, stackMember, st) # Check if the subtree rooted with v has a connection to # one of the ancestors of u # Case 1 (per above discussion on Disc and Low value) low[u] = min (low[u], low[v]) elif stackMember[v] = = True : '''Update low value of 'u' only if 'v' is still in stack (i.e. it's a back edge, not cross edge). Case 2 (per above discussion on Disc and Low value) ''' low[u] = min (low[u], disc[v]) # head node found, pop the stack and print an SCC w = - 1 #To store stack extracted vertices if low[u] = = disc[u]: while w ! = u: w = st.pop() print (w, end = " " ) stackMember[w] = False print () #The function to do DFS traversal. # It uses recursive SCCUtil() def SCC( self ): # Mark all the vertices as not visited # and Initialize parent and visited, # and ap(articulation point) arrays disc = [ - 1 ] * ( self .V) low = [ - 1 ] * ( self .V) stackMember = [ False ] * ( self .V) st = [] # Call the recursive helper function # to find articulation points # in DFS tree rooted with vertex 'i' for i in range ( self .V): if disc[i] = = - 1 : self .SCCUtil(i, low, disc, stackMember, st) # Create a graph given in the above diagram g1 = Graph( 5 ) g1.addEdge( 1 , 0 ) g1.addEdge( 0 , 2 ) g1.addEdge( 2 , 1 ) g1.addEdge( 0 , 3 ) g1.addEdge( 3 , 4 ) print ( "SSC in first graph " ) g1.SCC() g2 = Graph( 4 ) g2.addEdge( 0 , 1 ) g2.addEdge( 1 , 2 ) g2.addEdge( 2 , 3 ) print ( "nSSC in second graph " ) g2.SCC() g3 = Graph( 7 ) g3.addEdge( 0 , 1 ) g3.addEdge( 1 , 2 ) g3.addEdge( 2 , 0 ) g3.addEdge( 1 , 3 ) g3.addEdge( 1 , 4 ) g3.addEdge( 1 , 6 ) g3.addEdge( 3 , 5 ) g3.addEdge( 4 , 5 ) print ( "nSSC in third graph " ) g3.SCC() g4 = Graph( 11 ) g4.addEdge( 0 , 1 ) g4.addEdge( 0 , 3 ) g4.addEdge( 1 , 2 ) g4.addEdge( 1 , 4 ) g4.addEdge( 2 , 0 ) g4.addEdge( 2 , 6 ) g4.addEdge( 3 , 2 ) g4.addEdge( 4 , 5 ) g4.addEdge( 4 , 6 ) g4.addEdge( 5 , 6 ) g4.addEdge( 5 , 7 ) g4.addEdge( 5 , 8 ) g4.addEdge( 5 , 9 ) g4.addEdge( 6 , 4 ) g4.addEdge( 7 , 9 ) g4.addEdge( 8 , 9 ) g4.addEdge( 9 , 8 ) print ( "nSSC in fourth graph " ) g4.SCC(); g5 = Graph ( 5 ) g5.addEdge( 0 , 1 ) g5.addEdge( 1 , 2 ) g5.addEdge( 2 , 3 ) g5.addEdge( 2 , 4 ) g5.addEdge( 3 , 0 ) g5.addEdge( 4 , 2 ) print ( "nSSC in fifth graph " ) g5.SCC(); #This code is contributed by Neelam Yadav |
Javascript
<script> // Javascript program to find strongly connected // components in a given directed graph // using Tarjan's algorithm (single DFS) // This class represents a directed graph // using adjacency list representation class Graph{ // Constructor constructor(v) { this .V = v; this .adj = new Array(v); for (let i = 0; i < v; ++i) this .adj[i] = []; this .Time = 0; } // Function to add an edge into the graph addEdge(v, w) { this .adj[v].push(w); } // A recursive function that finds and prints strongly // connected components using DFS traversal // u --> The vertex to be visited next // disc[] --> Stores discovery times of visited vertices // low[] -- >> earliest visited vertex (the vertex with // minimum discovery time) that can be reached // from subtree rooted with current vertex // st -- >> To store all the connected ancestors (could be // part of SCC) // stackMember[] --> bit/index array for faster check // whether a node is in stack SCCUtil(u, low, disc, stackMember, st) { // Initialize discovery time and low value disc[u] = this .Time; low[u] = this .Time; this .Time += 1; stackMember[u] = true ; st.push(u); let n; // Go through all vertices adjacent to this for (let i of this .adj[u]) { n = i; if (disc[n] == -1) { this .SCCUtil(n, low, disc, stackMember, st); // Check if the subtree rooted with v // has a connection to one of the // ancestors of u // Case 1 (per above discussion on // Disc and Low value) low[u] = Math.min(low[u], low[n]); } else if (stackMember[n] == true ) { // Update low value of 'u' only if 'v' is // still in stack (i.e. it's a back edge, // not cross edge). // Case 2 (per above discussion on Disc // and Low value) low[u] = Math.min(low[u], disc[n]); } } // Head node found, pop the stack and print an SCC // To store stack extracted vertices let w = -1; if (low[u] == disc[u]) { while (w != u) { w = st.pop(); document.write(w + " " ); stackMember[w] = false ; } document.write( "<br>" ); } } // The function to do DFS traversal. // It uses SCCUtil() SCC() { // Mark all the vertices as not visited // and Initialize parent and visited, // and ap(articulation point) arrays let disc = new Array( this .V); let low = new Array( this .V); for (let i = 0;i < this .V; i++) { disc[i] = -1; low[i] = -1; } let stackMember = new Array( this .V); let st = []; // Call the recursive helper function // to find articulation points // in DFS tree rooted with vertex 'i' for (let i = 0; i < this .V; i++) { if (disc[i] == -1) this .SCCUtil(i, low, disc, stackMember, st); } } } // Driver code // Create a graph given in the above diagram let g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); document.write( "SSC in first graph <br>" ); g1.SCC(); let g2 = new Graph(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); document.write( "SSC in second graph<br> " ); g2.SCC(); let g3 = new Graph(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); document.write( "SSC in third graph <br>" ); g3.SCC(); let g4 = new Graph(11); g4.addEdge(0, 1); g4.addEdge(0, 3); g4.addEdge(1, 2); g4.addEdge(1, 4); g4.addEdge(2, 0); g4.addEdge(2, 6); g4.addEdge(3, 2); g4.addEdge(4, 5); g4.addEdge(4, 6); g4.addEdge(5, 6); g4.addEdge(5, 7); g4.addEdge(5, 8); g4.addEdge(5, 9); g4.addEdge(6, 4); g4.addEdge(7, 9); g4.addEdge(8, 9); g4.addEdge(9, 8); document.write( "SSC in fourth graph<br> " ); g4.SCC(); let g5 = new Graph (5); g5.addEdge(0, 1); g5.addEdge(1, 2); g5.addEdge(2, 3); g5.addEdge(2, 4); g5.addEdge(3, 0); g5.addEdge(4, 2); document.write( "SSC in fifth graph <br>" ); g5.SCC(); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
SCCs in first graph431 2 0SCCs in second graph3210SCCs in third graph53462 1 0SCCs in fourth graph8 975 4 63 2 1 010SCCs in fifth graph4 3 2 1 0
时间复杂性： 上述算法主要调用DFS，DFS对用邻接表表示的图取O（V+E）。
参考资料： http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm http://www.ics.uci.edu/~eppstein/161/960220。html#sca 本文由 导演 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
