Perbandingan algoritma Tarjan dan algoritma Kosaraju

Algoritma Tarjan adalah untuk mencari komponen terpaut kuat dalam graf terarah Robert Tarjan mencipta teknik lintasan graf yang dipanggil algoritma Tarjan pada tahun 1972. Daripada merentasi nod yang diproses sebelum ini, ia mengesan dan memproses setiap komponen yang sangat relevan dengan cekap menggunakan strategi carian mendalam-dahulukan dan struktur data tindanan. Algoritma ini kerap digunakan dalam sains komputer dan teori graf dan mempunyai pelbagai kegunaan, termasuk penciptaan algoritma, analisis rangkaian dan perlombongan data.

Algoritma Kosaraju terdiri daripada dua traversal graf. Dalam laluan pertama, graf dilalui dalam susunan terbalik dan setiap nod diberikan "masa penyiapan". Dalam laluan kedua, nod dilawati mengikut urutan masa penyiapannya dan setiap komponen yang bersambung kuat dikenal pasti dan dilabelkan.

Kaedah algoritma Tarjan

Dalam contoh ini, kelas Graf ditakrifkan pada permulaan program dan pembinanya memulakan tatasusunan senarai bersebelahan berdasarkan bilangan bucu dalam graf. Fungsi addEdge menambah kelebihan pada graf dengan memasukkan bucu sasaran dalam senarai bersebelahan bucu sumber.

Kaedah SCCUtil ialah fungsi rekursif berasaskan DFS yang digunakan oleh kaedah SCC untuk menemui SCC, dan ia menjadi asas kepada program ini. Puncak semasa u, tatasusunan cakera masa penemuan, tatasusunan nilai rendah rendah, tatasusunan timbunan bucu st, dan ahli timbunan, tatasusunan nilai Boolean yang menjejaki sama ada satu bucu berada pada tindanan, adalah input kepada fungsi ini.

Proses ini meletakkan bucu semasa ke dalam tindanan dan menukar nilai ahli tindanannya kepada benar selepas mula-mula memberikannya masa penemuan dan nilai yang rendah. Selepas itu, ia mengemas kini nilai rendah semua bucu berdekatan secara rekursif kepada bucu semasa.

Teknik ini secara berulang melawat bucu yang belum ditemui vs dan mengubah suai nilai rendah u. Jika v sudah berada pada timbunan, kaedah ini mengubah nilai u yang lebih rendah berdasarkan masa v ditemui.

Algoritma Tarjan

• Algoritma permulaan

• Mula melintasi carta

• Periksa Komponen Yang Bersambung Kuat

• Ulang sehingga semua nod telah dilawati

• Kembalikan komponen yang bersambung kuat

Kaedah ini mengeluarkan semua bucu dari tindanan sehingga bucu semasa u muncul, mencetak bucu yang timbul dan jika u ialah nod kepala (iaitu jika nilai rendahnya bersamaan dengan masa penemuannya), tetapkan nilai Ahli tindanannya kepada palsu.

Contoh

// C++ program to find the SCC 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 {
    // No. of vertices
    int V;

    // A dynamic array of adjacency lists
    list<int>* adj;

    // A Recursive DFS based function
    // used by SCC()
    void SCCUtil(int u, int disc[], int low[], stack<int>* st, bool stackMember[]);

    public:
    // Member functions
    Graph(int V);
    void addEdge(int v, int w);
    void SCC();
};

// Constructor
Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

// Function to add an edge to the graph
void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

// Recursive function to finds the SCC
// using DFS traversal
void Graph::SCCUtil(int u, int disc[],  int low[], stack<int>* st,  bool stackMember[]) {
    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) {
        // v is current adjacent of 'u'
        int v = *i;

        // 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 connection to
           // one of the ancestors of 'u'
            low[u] = min(low[u], low[v]);
        }

        // Update low value of 'u' only of
        // 'v' is still in stack
        else if (stackMember[v] == true)
            low[u] = min(low[u], disc[v]);
    }

    // head node found, pop the stack
    // and print an SCC

    // Store stack extracted vertices
    int w = 0;

    // If low[u] and disc[u]
    if (low[u] == disc[u]) {
    // Until stack st is empty
        while (st->top() != u) {
            w = (int)st->top();

            // Print the node
            cout << w << " ";
            stackMember[w] = false;
            st->pop();
        }
        w = (int)st->top();
        cout << w << "\n";
        stackMember[w] = false;
        st->pop();
    }
}

// Function to find the SCC in the graph
void Graph::SCC() {
    // Stores the discovery times of
    // the nodes
    int* disc = new int[V];

    // Stores the nodes with least
    // discovery time
    int* low = new int[V];

    // Checks whether a node is in
    // the stack or not
    bool* stackMember = new bool[V];

    // Stores all the connected ancestors
    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;
    }

    // Recursive helper function to
    // find the SCC in DFS tree with
    // vertex 'i'
    for (int i = 0; i < V; i++) {

        // If current node is not
        // yet visited
        if (disc[i] == NIL) {
            SCCUtil(i, disc, low, st, stackMember);
        }
    }
}

// Driver Code
int main() {
    // Given a graph
    Graph g1(5);
    g1.addEdge(3, 5);
    g1.addEdge(0, 2);
    g1.addEdge(2, 1);
    g1.addEdge(4, 3);
    g1.addEdge(3, 4);

    // Function Call to find SCC using
    // Tarjan's Algorithm
    g1.SCC();

    return 0;
} 

Output

1
2
0
4 3 

Kaedah 2-Kosaraju

Algoritma Kosaraju

• Buat koleksi nod yang dilawati dan timbunan kosong semasa permulaan.

• Mulakan carian mendalam-pertama dari nod pertama dalam graf yang belum dilawati lagi. Tolak setiap nod yang dilawati sepanjang carian ke dalam tindanan.

• Arah setiap tepi grafik hendaklah diterbalikkan.

• Jika tindanan masih penuh dengan nod, keluarkan nod dari tindanan. Jika nod belum dilawati, carian mendalam-pertama dilakukan daripada nod tersebut. Tandai setiap nod yang dilawati semasa carian sebagai ahli komponen terpaut tinggi semasa.

• Ulang sehingga semua nod telah dilawati

.

• Setiap komponen yang sangat bersambung akan dikenal pasti dan diberi penjelasan menjelang akhir program.

Kod C++ berikut menggunakan algoritma Kosaraju untuk mencari Komponen Bersambung Kuat (SCC) dalam graf terarah. Perisian ini mentakrifkan kelas bernama Graph, yang mempunyai fungsi ahli berikut:

Graf(int V): Pembina, masukkan bilangan bucu V dan mulakan senarai bersebelahan graf.

Void addEdge(int v, int w): Menggunakan dua integer v dan w sebagai input, kaedah ini mencipta tepi yang menghubungkan bucu v ke bucu w dalam graf.

fungsi void printSCCs() menggunakan algoritma Kosaraju untuk mencetak setiap SCC dalam graf.

Kaedah graf getTranspose() menyediakan transpose graf.

Gunakan fungsi rekursif void fillOrder(int v, bool Visited[, stack& Stack], int v) untuk menambah bucu pada tindanan mengikut urutan masa penyiapannya.

Contoh 2

// C++ program to print the SCC of the 
// graph using Kosaraju's Algorithm 
#include <iostream> 
#include <list>
#include <stack> 
using namespace std; 
 
class Graph {
   // No. of vertices 
   int V; 
    
   // An array of adjacency lists 
   list<int>* adj; 
    
   // Member Functions 
   void fillOrder(int v, bool visited[], 
   stack<int>& Stack); 
   void DFSUtil(int v, bool visited[]); 
    
   public: 
   Graph(int V); 
   void addEdge(int v, int w); 
   void printSCCs(); 
   Graph getTranspose(); 
}; 
 
// Constructor of class 
Graph::Graph(int V) { 
   this->V = V; 
   adj = new list<int>[V]; 
} 
 
// Recursive function to print DFS 
// starting from v 
void Graph::DFSUtil(int v, bool visited[])  { 
   // Mark the current node as 
   // visited and print it 
   visited[v] = true; 
   cout << v <<" "; 
    
   // Recur for all the vertices 
   // adjacent to this vertex 
   list<int>::iterator i; 
    
   // Traverse Adjacency List of node v 
   for (i = adj[v].begin(); 
   i != adj[v].end(); ++i) { 
       
      // If child node *i is unvisited 
      if (!visited[*i]) 
      DFSUtil(*i, visited); 
   } 
} 
 
// Function to get the transpose of 
// the given graph 
Graph Graph::getTranspose()  { 
   Graph g(V); 
   for (int v = 0; v < V; v++) { 
      // Recur for all the vertices 
      // adjacent to this vertex 
      list<int>::iterator i; 
      for (i = adj[v].begin(); 
      i != adj[v].end(); ++i) { 
         // Add to adjacency list 
         g.adj[*i].push_back(v); 
      } 
   } 
    
   // Return the reversed graph 
   return g; 
} 
 
// Function to add an Edge to the given 
// graph 
void Graph::addEdge(int v, int w)  { 
   // Add w to v’s list 
   adj[v].push_back(w); 
} 
 
// Function that fills stack with vertices 
// in increasing order of finishing times 
void Graph::fillOrder(int v, bool visited[], 
stack<int>& Stack)  { 
   // Mark the current node as 
   // visited and print it 
   visited[v] = true; 
    
   // Recur for all the vertices 
   // adjacent to this vertex 
   list<int>::iterator i; 
    
   for (i = adj[v].begin(); 
   i != adj[v].end(); ++i) { 
    
      // If child node *i is unvisited 
      if (!visited[*i]) { 
         fillOrder(*i, visited, Stack); 
      } 
   } 
    
   // All vertices reachable from v 
   // are processed by now, push v 
   Stack.push(v); 
} 
 
// Function that finds and prints all 
// strongly connected components 
void Graph::printSCCs()  { 
   stack<int> Stack; 
    
   // Mark all the vertices as 
   // not visited (For first DFS) 
   bool* visited = new bool[V]; 
   for (int i = 0; i < V; i++) 
   visited[i] = false; 
    
   // Fill vertices in stack according 
   // to their finishing times 
   for (int i = 0; i < V; i++) 
   if (visited[i] == false) 
   fillOrder(i, visited, Stack); 
    
   // Create a reversed graph 
   Graph gr = getTranspose(); 
    
   // Mark all the vertices as not 
   // visited (For second DFS) 
   for (int i = 0; i < V; i++) 
   visited[i] = false; 
    
   // Now process all vertices in 
   // order defined by Stack 
   while (Stack.empty() == false) { 
    
      // Pop a vertex from stack 
      int v = Stack.top(); 
      Stack.pop(); 
       
      // Print SCC of the popped vertex 
      if (visited[v] == false) { 
         gr.DFSUtil(v, visited); 
         cout << endl; 
      } 
   } 
} 
 
// Driver Code 
int main()  { 
   // Given Graph 
   Graph g(5); 
   g.addEdge(1, 0); 
   g.addEdge(0, 2); 
   g.addEdge(2, 1); 
   g.addEdge(1, 3); 
   g.addEdge(2, 4); 
    
   // Function Call to find the SCC 
   // using Kosaraju's Algorithm 
   g.printSCCs(); 
    
   return 0; 
} 

Output

0 1 2 
4
3</p><p>

Kesimpulan

Ringkasnya, kerumitan masa kaedah Tarjan dan Kosaraju ialah O(V + E), di mana V mewakili set bucu dalam graf dan E mewakili set tepi dalam graf. Faktor malar dalam algoritma Tarjan adalah jauh lebih rendah daripada faktor dalam kaedah Kosaraju. Kaedah Kosaraju merentasi graf sekurang-kurangnya dua kali, jadi faktor pemalar mungkin dua kali lebih tinggi. Apabila kami melengkapkan DFS kedua, kami boleh menggunakan kaedah Kosaraju untuk menjana SCC yang kini aktif. Sebaik sahaja kepala subtree SCC ditemui, mencetak SCC mengambil masa yang lebih lama dengan algoritma Tarjan.

Walaupun kerumitan masa linear kedua-dua kaedah adalah sama, terdapat beberapa perbezaan dalam kaedah atau proses yang digunakan untuk pengiraan SCC. Walaupun teknik Kosaraju menjalankan dua DFS pada graf (atau tiga DFS jika kita ingin mengekalkan graf asal tidak diubah suai) dan sangat serupa dengan kaedah menentukan susunan topologi graf, kaedah Tarjan hanya bergantung pada rekod nod DFS membahagikan graf .

Atas ialah kandungan terperinci Perbandingan algoritma Tarjan dan algoritma Kosaraju. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!