Vergleich des Tarjan-Algorithmus und des Kosaraju-Algorithmus

Tarjans Algorithmus dient zum Auffinden stark verknüpfter Komponenten in einem gerichteten Graphen. Robert Tarjan entwickelte 1972 eine Graph-Traversal-Technik namens Tarjans Algorithmus. Anstatt zuvor verarbeitete Knoten zu durchqueren, lokalisiert und verarbeitet es effizient jede hochrelevante Komponente mithilfe von Tiefensuchstrategien und Stapeldatenstrukturen. Der Algorithmus wird häufig in der Informatik und der Graphentheorie verwendet und hat vielfältige Einsatzmöglichkeiten, darunter die Erstellung von Algorithmen, die Netzwerkanalyse und das Data Mining.

Kosarajus Algorithmus besteht aus zwei Durchläufen des Graphen. Im ersten Durchgang wird der Graph in umgekehrter Reihenfolge durchlaufen und jedem Knoten wird eine „Abschlusszeit“ zugewiesen. Im zweiten Durchgang werden die Knoten in der Reihenfolge ihrer Fertigstellungszeit besucht und jede stark verbundene Komponente wird identifiziert und gekennzeichnet.

Tarjan-Algorithmus-Methode

In diesem Beispiel wird die Graph-Klasse am Anfang des Programms definiert und ihr Konstruktor initialisiert das Adjazenzlisten-Array basierend auf der Anzahl der Scheitelpunkte im Diagramm. Die Funktion addEdge fügt dem Diagramm eine Kante hinzu, indem sie den Zielscheitelpunkt in die Adjazenzliste des Quellscheitelpunkts aufnimmt.

Die SCCUtil-Methode ist eine DFS-basierte rekursive Funktion, die von der SCC-Methode zum Erkennen von SCCs verwendet wird, und bildet die Grundlage dieses Programms. Der aktuelle Scheitelpunkt u, ein Array mit Erkennungszeiten der Scheibe, ein Array mit niedrigen Werten low, ein Array mit dem Scheitelpunktstapel st und stackMember, ein Array mit booleschen Werten, das verfolgt, ob sich ein Scheitelpunkt auf dem Stapel befindet. sind die Eingaben für diese Funktion.

Dieser Prozess fügt den aktuellen Scheitelpunkt in den Stapel ein und ändert seinen StackMember-Wert in „True“, nachdem ihm zunächst eine Erkennungszeit und ein niedriger Wert zugewiesen wurden. Danach werden die niedrigen Werte aller nahegelegenen Scheitelpunkte rekursiv auf den aktuellen Scheitelpunkt aktualisiert.

Diese Technik besucht iterativ unentdeckte Scheitelpunkte vs und modifiziert niedrige Werte von u. Wenn sich v bereits auf dem Stapel befindet, ändert diese Methode den unteren Wert von u basierend auf dem Zeitpunkt, zu dem v entdeckt wurde.

Tarjan-Algorithmus

• Initialisierungsalgorithmus

• Beginnen Sie mit dem Durchlaufen der Karte

• Überprüfen Sie stark verbundene Komponenten

• Wiederholen, bis alle Knoten besucht wurden

• Fest verbundene Komponenten zurückgeben

Diese Methode entfernt alle Scheitelpunkte aus dem Stapel, bis der aktuelle Scheitelpunkt u entfernt wird, druckt die entfernten Scheitelpunkte und setzt, wenn u der Hauptknoten ist (d. h. wenn sein niedriger Wert gleich seiner Entdeckungszeit ist), seinen stackMember-Wert auf false.

Beispiel

// 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;
} 

Ausgabe

1
2
0
4 3 

Methode 2-Kosaraju

Kosaraju-Algorithmus

• Erstellen Sie beim Start eine Sammlung besuchter Knoten und einen leeren Stapel.

• Starten Sie eine Tiefensuche ab dem ersten Knoten im Diagramm, der noch nicht besucht wurde. Schieben Sie jeden während der Suche besuchten Knoten auf den Stapel.

• Die Richtung jeder Grafikkante sollte umgekehrt werden.

• Wenn der Stapel immer noch voller Knoten ist, entfernen Sie den Knoten vom Stapel. Wenn der Knoten nicht besucht wurde, wird von diesem Knoten aus eine Tiefensuche durchgeführt. Markieren Sie jeden während der Suche besuchten Knoten als Mitglied der aktuell stark verknüpften Komponente.

• Wiederholen, bis alle Knoten besucht wurden

.

• Jede hochgradig vernetzte Komponente wird am Ende des Programms identifiziert und kommentiert.

Der folgende C++-Code verwendet den Kosaraju-Algorithmus, um stark verbundene Komponenten (SCC) in einem gerichteten Diagramm zu finden. Die Software definiert eine Klasse namens Graph, die über die folgenden Mitgliedsfunktionen verfügt:

Graph(int V): Konstruktor, geben Sie die Anzahl der Scheitelpunkte V ein und initialisieren Sie die Adjazenzliste des Diagramms.

Void addEdge(int v, int w): Unter Verwendung zweier Ganzzahlen v und w als Eingabe erstellt diese Methode eine Kante, die den Scheitelpunkt v mit dem Scheitelpunkt w im Diagramm verbindet.

Die Funktion „void printSCCs()“ verwendet den Kosaraju-Algorithmus, um jeden SCC im Diagramm zu drucken.

Die Methode „Graph getTranspose()“ liefert die Transponierung des Diagramms.

Verwenden Sie die rekursive Funktion void fillOrder(int v, bool Visited[, stack& Stack], int v), um Scheitelpunkte in der Reihenfolge ihrer Fertigstellungszeit zum Stapel hinzuzufügen.

Beispiel 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; 
} 

Ausgabe

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

Fazit

Zusammenfassend beträgt die zeitliche Komplexität der Methode von Tarjan und Kosaraju O(V + E), wobei V die Menge der Eckpunkte im Diagramm und E die Menge der Kanten im Diagramm darstellt. Die konstanten Faktoren im Tarjan-Algorithmus sind deutlich niedriger als die im Kosaraju-Verfahren. Kosarajus Methode durchläuft den Graphen mindestens zweimal, sodass der konstante Faktor wahrscheinlich doppelt so hoch ist. Wenn wir das zweite DFS abgeschlossen haben, können wir die Methode von Kosaraju verwenden, um das jetzt aktive SCC zu generieren. Sobald der Kopf des SCC-Teilbaums gefunden ist, dauert das Drucken des SCC mit dem Tarjan-Algorithmus länger.

Obwohl die lineare Zeitkomplexität beider Methoden gleich ist, gibt es einige Unterschiede in den Methoden oder Prozessen, die für die SCC-Berechnung verwendet werden. Während Kosarajus Technik zwei DFS auf dem Graphen ausführt (oder drei DFS, wenn wir den ursprünglichen Graphen unverändert lassen möchten) und der Methode zur Bestimmung der topologischen Reihenfolge eines Graphen sehr ähnlich ist, basiert Tarjans Methode nur auf Knotendatensätzen. DFS partitioniert den Graphen .

Das obige ist der detaillierte Inhalt vonVergleich des Tarjan-Algorithmus und des Kosaraju-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!