Explicación del Algoritmo para encontrar puntos de articulación o vértices cortados de un gráfico

Voy a tratar de desarrollar una comprensión intuitiva sobre cómo funciona este algoritmo y también dar pseudocódigo comentado que produce Bi-Componentes, así como puentes.

En realidad es fácil desarrollar un algoritmo de fuerza bruta para los puntos de articulación. Simplemente saque un vértice y ejecute BFS o DFS en un gráfico. Si permanece conectado, entonces el vértice no es un punto de articulación, de lo contrario lo es. Esto se ejecutará en O(V(E+V)) = O(EV) tiempo. El desafío es cómo hacer esto en el tiempo lineal (es decir, O(E+V)).

Los puntos de articulación conectan dos (o más) subgrafos. Esto significa que no hay bordes de un subgrafo a otro. Así que imagina que estás dentro de uno de estos subgrafos y visitando su nodo. A medida que visita el nodo, lo marca y luego pasa al siguiente nodo sin marcar utilizando alguna arista disponible. Mientras estás haciendo esto, ¿cómo sabes que estás dentro del mismo subgrafo? La idea aquí es que si estás dentro del mismo subgrafo, eventualmente verás un nodo marcado a través de un borde mientras se visita un nodo sin marcar. Esto se llama un borde posterior e indica que usted tiene un ciclo. Tan pronto como encuentre un borde posterior, puede estar seguro de que todos los nodos a través de ese nodo marcado al que está visitando ahora son parte del mismo subgrafo y no hay puntos de articulación entre ellos. Si no vio ningún borde posterior, entonces todos los nodos que visitó hasta ahora son todos puntos de articulación.

Así que necesitamos un algoritmo que visite los vértices y marque todos puntos entre el objetivo de los bordes posteriores como nodos actualmente visitados como dentro del mismo subgrafo. Obviamente puede haber subgrafos dentro de subgrafos, por lo que necesitamos seleccionar el subgrafo más grande que tenemos hasta ahora. Estos subgrafos se llaman Bi-Componentes. Podemos implementar este algoritmo asignando a cada bi-componente un ID que se inicializa como un recuento del número de vértices que hemos visitado hasta ahora. Más tarde, a medida que encontremos bordes traseros, podemos restablecer el ID de bi-compinent al más bajo que tengamos encontrado hasta ahora.

Obviamente necesitamos dos pases. En el primer paso, queremos averiguar qué vértice podemos ver desde cada vértice a través de los bordes posteriores, si los hay. En la segunda pasada queremos visitar los vértices en la dirección opuesta y recoger el ID mínimo de bi-componente (es decir, el antepasado más antiguo accesible desde cualquier descendiente). DFS encaja naturalmente aquí. En DFS bajamos primero y luego volvemos a subir para que los dos pases anteriores se puedan hacer en un solo recorrido DFS.

Ahora sin además, aquí está el pseudocódigo:

time = 0
visited[i] = false for all i
GetArticulationPoints(u)
    visited[u] = true
    u.st = time++
    u.low = v.st    //keeps track of highest ancestor reachable from any descendants
    dfsChild = 0    //needed because if no child then removing this node doesn't decompose graph
    for each ni in adj[i]
        if not visited[ni]
            GetArticulationPoints(ni)
            ++dfsChild
            parents[ni] = u
            u.low = Min(u.low, ni.low)  //while coming back up, get the lowest reachable ancestor from descendants
        else if ni <> parent[u] //while going down, note down the back edges
            u.low = Min(u.low, ni.st)

    //For dfs root node, we can't mark it as articulation point because 
    //disconnecting it may not decompose graph. So we have extra check just for root node.
    if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
        Output u as articulation point
        Output edges of u with v.low >= u.low as bridges
    output u.low as bicomponent ID

Si low de la descendiente de u es mayor que el dfsnum de u, entonces u se dice que es el Punto de Articulación.

int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];

void cutvertex(int u){
    low[u]=dfsnum[u]=num++;
    for (int v = 0; v < 256; ++v)
    {
        if(adjMatrix[u][v] && dfsnum[v]==-1)
        {
            cutvertex(v);
            if(low[v]>dfsnum[u])    
                cout<<"Cut Vertex: "<<u<<"\n";
            low[u]=min(low[u], low[v]);
        }
        else{
            low[u]=min(low[u], dfsnum[v]);
        }
    }
}