Tarjan算法查找强联通组件的程序

本文给出了C++程序和Python程序。

tarjan算法是由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。

程序来源：Tarjan’s Algorithm to find Strongly Connected Components。

维基百科：Tarjan's strongly connected components algorithm。　

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