Comparación entre el algoritmo de Tarjan y Kosaraju

Algoritmo de Tarjan :el algoritmo de Tarjan es un algoritmo de gráfico eficiente que se utiliza para encontrar el SCC del componente fuertemente conectado en un gráfico dirigido mediante el uso de solo unrecorrido DFSen complejidad de tiempo lineal.

Laboral:

• Realice un recorrido DFS sobre los Nodes para que los subárboles de los componentes fuertemente conectados se eliminen cuando se encuentren.
• Luego se asignan dos valores:
  • El primer valor es el valor del contador cuando se explora el Node por primera vez.
  • El segundo valor almacena el valor de Node más bajo accesible desde el Node inicial que no forma parte de otro SCC .
• Cuando se exploran los Nodes, se colocan en una pila .
• Si quedan hijos de un Node sin explorar, se exploran y el valor asignado se actualiza respectivamente.

A continuación se muestra el programa para encontrar el SCC del gráfico dado usando el Algoritmo de Tarjan:

// 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(1, 0);
    g1.addEdge(0, 2);
    g1.addEdge(2, 1);
    g1.addEdge(0, 3);
    g1.addEdge(3, 4);
 
    // Function Call to find SCC using
    // Tarjan's Algorithm
    g1.SCC();
 
    return 0;
}

4
3
1 2 0

Algoritmo de Kosaraju :de Kosaraju también es unbúsqueda en profundidadque se utiliza para encontrar elSCCen un gráfico dirigido en una complejidad de tiempo lineal. El concepto básico de este algoritmo es que si podemos llegar al vérticevinicialmente a partir del vérticeu, entonces deberíamos poder llegar al vérticeua partir del vérticev, y si esta es la situación, podemos decir y concluir que los vérticesuyvestán fuertemente conectados, y están en el subgrafo fuertemente conectado.

Laboral:

• Realice un recorrido DFS en el gráfico dado, realizando un seguimiento de los tiempos de finalización de cada Node. Este proceso se puede realizar utilizando una pila .
• Cuando finalice el procedimiento de ejecutar el recorrido DFS sobre el gráfico, coloque el vértice de origen en la pila. De esta forma, el Node con el mayor tiempo de finalización estará en la parte superior de la pila.
• Invierta el gráfico original utilizando una lista de adyacencia .
• Luego realice otro recorrido DFS en el gráfico invertido con el vértice de origen como el vértice en la parte superior de la pila. Cuando finaliza el DFS que se ejecuta en el gráfico invertido, todos los Nodes que se visitan formarán un componente fuertemente conectado.
• Si quedan más Nodes o permanecen sin visitar, esto significa la presencia de más de un componente fuertemente conectado en el gráfico.
• Así que haga estallar los vértices desde la parte superior de la pila hasta que se encuentre un Node no visitado válido. Este tendrá el tiempo de finalización más alto de todos los Nodes actualmente no visitados.

A continuación se muestra el programa para encontrar el SCC del gráfico dado usando el Algoritmo de Kosaraju:

// 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(0, 3);
    g.addEdge(3, 4);
 
    // Function Call to find the SCC
    // using Kosaraju's Algorithm
    g.printSCCs();
 
    return 0;
}

0 1 2 
3 
4

Complejidad temporal :
la complejidad temporal del algoritmo de Tarjan y el algoritmo de Kosaraju será O(V + E) , donde V representa el conjunto de vértices y E representa el conjunto de aristas del gráfico. El algoritmo de Tarjan tiene factores constantes mucho más bajos que el algoritmo de Kosaraju. En el algoritmo de Kosaraju, el recorrido del gráfico se realiza al menos 2 veces, por lo que el factor constante puede ser el doble del tiempo. Podemos imprimir el SCC en progreso con el algoritmo de Kosaraju mientras realizamos el segundo DFS. Al realizar el Algoritmo de Tarjan, se requiere más tiempo para imprimir el SCC después de encontrar el encabezado del subárbol de SCC .

Resumen :
Ambos métodos tienen la misma complejidad de tiempo lineal, pero las técnicas o el procedimiento para los cálculos de SCC son bastante diferentes. El método de Tarjan depende únicamente del registro de Nodes en un DFS para particionar el gráfico, mientras que el método de Kosaraju realiza los dos DFS (o 3 DFS si queremos dejar el gráfico original sin cambios) en el gráfico y es bastante similar al método para encontrar el Clasificación topológica de un grafo.