本文給出了C++程序和Python程序。
tarjan算法是由Robert Tarjan提出的求解有向圖強連通分量的線性時間的算法。
程序來源：Tarjan’s Algorithm to find Strongly Connected Components。
百度百科：tarjan算法。維基百科：Tarjan's strongly connected components algorithm?！?/p>參考文章：Tarjan算法。
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 -1using namespace std; // A class that represents an directed graphclass 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 stackvoid 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 << "/n"; 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 functionint main(){ cout << "/nSCCs in first graph /n"; 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 << "/nSCCs in second graph /n"; Graph g2(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.SCC(); cout << "/nSCCs in third graph /n"; 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 << "/nSCCs in fourth graph /n"; 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 << "/nSCCs in fifth graph /n"; 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;}程序運行輸出：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 Python程序：# 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 representationclass 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, 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 diagramg1 = 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
新聞熱點
疑難解答
