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é.
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 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.
// C++ program to find the SCC using // Tarjan's algorithm (single DFS) #include#include #include
#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 * adj; // A Recursive DFS based function // used by SCC() void SCCUtil(int u, int disc[], int low[], stack * 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 [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 * 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 ::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 * st = new stack (); // 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; }
1 2 0 4 3
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 fonctionvoid 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.
// C++ program to print the SCC of the // graph using Kosaraju's Algorithm #include#include #include
using namespace std; class Graph { // No. of vertices int V; // An array of adjacency lists list * adj; // Member Functions void fillOrder(int v, bool visited[], stack & 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 [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 ::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 ::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 & Stack) { // Mark the current node as // visited and print it visited[v] = true; // Recur for all the vertices // adjacent to this vertex list ::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 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; }
0 1 2 4 3
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!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
