Spiegazione dell'algoritmo per trovare punti di articolazione o tagliare vertici di un grafico

Question

Ho cercato la rete e non ho trovato alcuna spiegazione di un algoritmo DFS per trovare tutti i vertici di articolazione di un grafico. Non c'è nemmeno una pagina wiki.

Dalla lettura in giro, ho avuto modo di conoscere i fatti di base da qui. PDF

C'è una variabile in ogni nodo che guarda effettivamente i bordi posteriori e trova il nodo più vicino e più in alto verso il nodo radice. Dopo aver elaborato tutti i bordi sarebbe stato trovato.

Ma non riesco a capire come trovare questa variabile su & su ciascun nodo durante l'esecuzione di DFS. Che cosa fa esattamente questa variabile?

Si prega di spiegare l'algoritmo.

Grazie.

Answer 1

Trovare i vertici di articolazione è un'applicazione di DFS.

In poche parole,

1. Applicare DFS su un grafico. Ottieni l'albero DFS.
2. Un nodo che viene visitato in precedenza è un "genitore" di quei nodi che sono raggiunti da esso e visitato in seguito.
3. Se un figlio di un nodo non ha un percorso per nessuno dei suoi antenati, significa che la rimozione di questo nodo renderebbe questo bambino disgiunto dal grafico.
4. C'è un'eccezione: la radice dell'albero. Se ha più di un figlio, allora è un punto di articolazione, altrimenti no.

Punto 3 significa essenzialmente che questo nodo è un punto di articolazione.

Ora per un bambino, questo percorso verso gli antenati del nodo passerebbe da un lato posteriore o da uno dei suoi figli.

Tutto questo è spiegato magnificamente in questo PDF.

Answer 2

Se low del discendente di u è maggiore della dfsnum di u, poi u si dice che sia l'articolazione Point.

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

Answer 3

Cercherò di sviluppare una comprensione intuitiva su come funziona questo algoritmo funziona e anche dare pseudocodice commentato che emette Bi-Componenti e ponti.

In realtà è facile sviluppare un algoritmo di forza bruta per i punti di articolazione. Basta estrarre un vertice ed eseguire BFS o DFS su un grafico. Se rimane connesso, il vertice non è un punto di articolazione, altrimenti lo è. Questo verrà eseguito nel tempo O(V(E+V)) = O(EV). La sfida è come farlo in tempo lineare (ad esempio O(E+V)).

I punti di articolazione collegano due (o più) sottografi. Questo significa che non ci sono bordi da un sottografo all'altro. Quindi immagina di essere all'interno di uno di questi sottografi e di visitare il suo nodo. Quando visiti il ​​nodo, lo contrassegni e poi passerai al prossimo nodo non infilato usando un margine disponibile. Mentre lo fai, come fai a sapere di trovarti nello stesso sottografo?L'intuizione qui è che se ci si trova all'interno dello stesso sottografo, alla fine si vedrà un nodo contrassegnato attraverso un fronte mentre si visita un nodo non flagellato. Questo è chiamato un bordo posteriore e indica che hai un ciclo. Non appena trovi un margine posteriore, puoi essere certo che tutti i nodi attraverso quel nodo contrassegnato a quello che stai visitando in questo momento fanno tutti parte dello stesso sottografo e non ci sono punti di articolazione tra loro. Se non hai visto alcun bordo posteriore, tutti i nodi che hai visitato fino a quel momento sono tutti punti di articolazione.

Quindi abbiamo bisogno di un algoritmo che visita i vertici e contrassegna tutti i punti tra la destinazione dei bordi posteriori come attualmente visitati, nodi come all'interno dello stesso sottografo. Potrebbero ovviamente esserci dei sottografi all'interno dei sottografi, quindi è necessario selezionare il sottografo più grande che abbiamo finora. Questi sottografi sono chiamati Bi-Components. Possiamo implementare questo algoritmo assegnando ad ogni bi-componente un ID che è inizializzato come solo un conteggio del numero di vertici che abbiamo visitato finora. Più tardi, quando troviamo i bordi indietro, possiamo resettare l'ID bi-compinent al più basso che abbiamo trovato finora.

Ovviamente abbiamo bisogno di due passaggi. Nel primo passaggio, vogliamo capire quale vertice possiamo vedere da ogni vertice attraverso i bordi posteriori, se ce ne sono. Nel secondo passaggio vogliamo visitare i vertici nella direzione opposta e raccogliere l'ID bi-componente minimo (cioè l'antenato più antico accessibile da qualsiasi discendente). DFS si adatta naturalmente qui. In DFS scendiamo per primi e poi torniamo indietro in modo che entrambi i passaggi precedenti possano essere eseguiti in una singola traversal DFS.

Ora, senza ulteriori indugi, ecco il pseudocodice:

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