Explication de L'algorithme pour trouver les points d'articulation ou les sommets coupés d'un graphe

je vais essayer de développer une compréhension intuitive sur la façon dont cet algorithme fonctionne et donner également commenté pseudocode qui produit Bi-composants ainsi que des ponts.

il est en fait facile de développer un algorithme de force brute pour les points d'articulation. Il suffit de prendre un vertex, et exécuter BFS ou DFS sur un graphique. Si il reste connecté, puis le sommet n'est pas un point d'articulation, sinon il est. Cela se déroulera dans le temps O(V(E+V)) = O(EV) . Le défi est de savoir comment faire en linéaire temps (c'est à dire O(E+V) ).

l'Articulation des points de connecter deux (ou plus) les sousgraphes. Cela signifie qu'il y a pas d'arêtes d'un graphe à l'autre. Alors imaginez que vous êtes dans l'un de ces sous-paragraphes et que vous visitez son nœud. Lorsque vous visitez le noeud, vous le Marquez et vous passez ensuite au prochain noeud non divisé en utilisant un bord disponible. Pendant que vous faites ça, comment savez-vous que vous êtes toujours dans le même sous-paragraphe? L'intuition, c'est que si vous êtes dans le même sous-graphe, vous éventuellement voir un noeud flagged à travers un bord tout en visitant un noeud non flagged. Cela s'appelle un bord arrière et indique que vous avez un cycle. Dès que vous trouvez un bord arrière, vous pouvez être sûr que tous les noeuds à travers ce noeud signalé à celui que vous visitez en ce moment font tous partie du même sous-graphe et il n'y a aucun point d'articulation entre les deux. Si vous n'avez pas vu de bordures arrières, alors tous les noeuds que vous avez visités jusqu'à présent sont tous des points d'articulation.

donc nous besoin d'un algorithme qui visite les sommets et marque Tous les points entre la cible des bords arrière comme actuellement-être-visité noeuds que dans le même sous-graphe. Il peut évidemment être sousgraphes dans les sousgraphes donc, nous devons sélectionner plus grand sous-graphe nous avons jusqu'à présent. Ces sous-paragraphes sont appelés Bi-Components. Nous pouvons implémenter cet algorithme en assignant à chaque bi-component un ID qui est initialisé comme un simple compte du nombre de Sommets que nous avons visités jusqu'à présent. Plus tard, comme nous l' trouver les contours arrières, nous pouvons réinitialiser l'ID du bi-compinant au plus bas que nous avons trouvé jusqu'à présent.

il nous faut évidemment deux laissez-passer. Dans le premier passage, nous voulons savoir quel vertex nous pouvons voir à partir de chaque vertex à travers les bords arrières, s'il y en a. Dans le second passage nous voulons visiter les sommets dans la direction opposée et recueillir le minimum bi-composant ID (c.-à-d. ancêtre le plus ancien accessible de tous les descendants). DFS s'inscrit naturellement ici. À la DSV, nous descendons en premier, puis nous remontons pour que les deux des passes ci-dessus peuvent être faites dans un seul DFS traversal.

sans plus attendre, voici le pseudo:

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 du descendant de u est supérieur à dfsnum de u , alors u est considéré comme le Point d'Articulation.

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]);
        }
    }
}