Comparaison de l'algorithme de Tarjan et de l'algorithme de Kosaraju

L'algorithme de Tarjan permet de localiser des composants fortement liés dans un graphe orienté Robert Tarjan a créé une technique de parcours de graphe appelée algorithme de Tarjan en 1972. Au lieu de parcourir les nœuds précédemment traités, il localise et traite efficacement chaque composant hautement pertinent à l'aide de stratégies de recherche en profondeur et de structures de données de pile. L'algorithme est fréquemment utilisé en informatique et en théorie des graphes et a diverses utilisations, notamment la création d'algorithmes, l'analyse de réseaux et l'exploration de données.

L'algorithme de Kosaraju consiste en deux parcours du graphique. Lors du premier passage, le graphique est parcouru dans l'ordre inverse et chaque nœud se voit attribuer un « temps d'achèvement ». Lors de la deuxième passe, les nœuds sont visités par ordre d'heure d'achèvement et chaque composant fortement connecté est identifié et étiqueté.

Méthode de l'algorithme de Tarjan

Dans cet exemple, la classe Graph est définie au début du programme et son constructeur initialise le tableau de liste de contiguïté en fonction du nombre de sommets dans le graphe. La fonction addEdge ajoute une arête au graphique en incluant le sommet cible dans la liste de contiguïté du sommet source.

La méthode SCCUtil est une fonction récursive basée sur DFS utilisée par la méthode SCC pour découvrir les SCC, et elle constitue la base de ce programme. Le sommet actuel u, un tableau de temps de découverte disc, un tableau de valeurs faibles, un tableau de pile de sommets st et stackMember, un tableau de valeurs booléennes qui permet de savoir si un sommet est sur la pile, sont les entrées de cette fonction.

Ce processus place le sommet actuel dans la pile et change sa valeur stackMember en true après lui avoir d'abord attribué un temps de découverte et une valeur faible. Après cela, il met à jour de manière récursive les valeurs faibles de tous les sommets proches vers le sommet actuel.

Cette technique visite de manière itérative les sommets non découverts vs et modifie les faibles valeurs de u. Si v est déjà sur la pile, cette méthode modifie la valeur inférieure de u en fonction de l'heure à laquelle v a été découvert.

Algorithme de Tarjan

• Algorithme d'initialisation

• Commencez à parcourir le graphique

• Vérifiez les composants fortement connectés

• Répétez jusqu'à ce que tous les nœuds aient été visités

• Renvoyer les composants fortement connectés

Cette méthode fait apparaître tous les sommets de la pile jusqu'à ce que le sommet actuel u soit sauté, imprime les sommets sautés et si u est le nœud principal (c'est-à-dire si sa valeur basse est égale à son temps de découverte), définit sa valeur stackMember sur false.

Exemple

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

Sortie

1
2
0
4 3 

Méthode 2-Kosaraju

Algorithme Kosaraju

• Créez une collection de nœuds visités et une pile vide au démarrage.

• Démarrez une recherche en profondeur à partir du premier nœud du graphique qui n'a pas encore été visité. Poussez chaque nœud visité tout au long de la recherche sur la pile.

• La direction de chaque bord graphique doit être inversée.

• Si la pile est encore pleine de nœuds, retirez le nœud de la pile. Si le nœud n'a pas été visité, une recherche en profondeur d'abord est effectuée à partir de ce nœud. Marquez chaque nœud visité lors de la recherche comme membre du composant hautement lié actuel.

• Répétez jusqu'à ce que tous les nœuds aient été visités

.

• Chaque composant hautement connecté sera identifié et annoté d'ici la fin du programme.

Le code C++ suivant utilise l'algorithme de Kosaraju pour trouver des composants fortement connectés (SCC) dans un graphe orienté. Le logiciel définit une classe nommée Graph, qui possède les fonctions membres suivantes :

Graph(int V) : Constructeur, saisissez le nombre de sommets V et initialisez la liste de contiguïté du graphe.

Void addEdge(int v, int w) : en utilisant deux entiers v et w comme entrée, cette méthode crée une arête reliant le sommet v au sommet w dans le graphique.

La fonction

void printSCCs() utilise l'algorithme de Kosaraju pour imprimer chaque SCC dans le graphique.

La méthode Graph getTranspose() fournit la transposition du graphique.

Utilisez la fonction récursive void fillOrder(int v, bool Visited[, stack& Stack], int v) pour ajouter des sommets à la pile dans l'ordre de leur heure d'achèvement.

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

Sortie

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

Conclusion

En résumé, la complexité temporelle de la méthode de Tarjan et Kosaraju est O(V + E), où V représente l'ensemble des sommets du graphe et E représente l'ensemble des arêtes du graphe. Les facteurs constants de l'algorithme de Tarjan sont nettement inférieurs à ceux de la méthode de Kosaraju. La méthode de Kosaraju parcourt le graphique au moins deux fois, donc le facteur constant est probablement deux fois plus élevé. Lorsque nous aurons terminé le deuxième DFS, nous pourrons utiliser la méthode de Kosaraju pour générer le SCC désormais actif. Une fois la tête du sous-arbre SCC trouvée, l’impression du SCC avec l’algorithme Tarjan prend plus de temps.

Bien que la complexité temporelle linéaire des deux méthodes soit la même, il existe certaines différences dans les méthodes ou processus utilisés pour le calcul du SCC. Alors que la technique de Kosaraju exécute deux DFS sur le graphe (ou trois DFS si l'on souhaite conserver le graphe d'origine inchangé) et est très similaire à la méthode de détermination de l'ordre topologique d'un graphe, la méthode de Tarjan s'appuie uniquement sur les enregistrements de nœuds DFS partitionne le graphe. .

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!