Wyjaśnienie algorytmu do znajdowania punktów artykulacji lub przecięcia wierzchołków wykresu

Question

Przeszukałem sieć i nie mogłem znaleźć żadnego wyjaśnienia algorytmu DFS do znajdowania wszystkich wierzchołków przegubu na wykresie. Nie ma nawet strony wiki.

Od przeczytania, poznałem podstawowe fakty z tego miejsca. PDF

W każdym węźle znajduje się zmienna, która faktycznie patrzy na tylne krawędzie i znajduje najbliższy i najwyższy węzeł w kierunku węzła głównego. Po przetworzeniu wszystkich krawędzi zostanie znaleziony.

Ale nie rozumiem, jak znaleźć to w dół & do zmiennej w każdym węźle podczas wykonywania DFS. Co dokładnie robi ta zmienna?

Proszę wyjaśnić algorytm.

Dzięki.

Answer 1

Wyszukiwanie wierzchołków przegubowych to aplikacja systemu plików DFS.

W skrócie,

1. Zastosuj DFS na wykresie. Pobierz drzewo DFS.
2. Węzeł, który jest odwiedzany wcześniej, jest "rodzica" tych węzłów, które są osiągane i odwiedzane później.
3. Jeśli dowolne dziecko węzła nie ma ścieżki do żadnego z przodków jego rodzica, oznacza to, że usunięcie tego węzła spowodowałoby rozłączenie tego dziecka na wykresie.
4. Istnieje wyjątek: katalog główny drzewa. Jeśli ma więcej niż jedno dziecko, jest to punkt przegubowy, w przeciwnym razie nie.

Punkt 3 zasadniczo oznacza, że ​​ten węzeł jest punktem przegubowym.

Teraz dla dziecka, ta ścieżka do przodków węzła będzie przez tylną krawędź z niego lub z dowolnego z jego dzieci.

Wszystko to jest pięknie wyjaśnione w tym PDF.

Answer 2

Jeśli low o potomka u jest większa niż dfsnum z u, następnie u mówi się, że punkt artykulacji.

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

Postaram się rozwijać intuicyjne zrozumienie, w jaki sposób ten algorytm robót, a także dać skomentował Pseudokod że wyprowadza dwuskładnikowych oraz mosty.

W rzeczywistości łatwo jest opracować algorytm o silnej sile dla punktów przegubowych. Po prostu wyłóż wierzchołek i uruchom BFS lub DFS na wykresie. Jeśli pozostaje połączony, wówczas wierzchołek nie jest punktem przegubowym, w przeciwnym razie jest. To będzie działać w czasie O(V(E+V)) = O(EV). Wyzwaniem jest, jak to zrobić w czasie liniowym (to jest O(E+V)).

Punkty przegubu łączą dwie (lub więcej) podgrafy. Oznacza to, że nie ma żadnych krawędzi od jednego subgraphu do drugiego. Więc wyobraź sobie, że jesteś w jednej z tych podgraf i odwiedzasz jej węzeł. Podczas odwiedzania węzła należy go zgłosić, a następnie przejść do następnego niezatwierdzonego węzła, korzystając z dostępnej krawędzi. Kiedy to robisz, skąd wiesz, że wciąż jesteś w tym samym podkatalogu?Wgląd w to, że jeśli jesteś w obrębie tego samego subgraph, ostatecznie zobaczysz flagowany węzeł przez krawędź podczas odwiedzania niezatwierdzonego węzła. To się nazywa tylna krawędź i oznacza, że ​​masz cykl. Jak tylko znajdziesz tylną krawędź, możesz być pewien, że wszystkie węzły przechodzące przez ten oznaczony węzeł do tego, który odwiedzasz teraz, są częścią tego samego subgraphu i nie ma między nimi żadnych punktów artykulacji. Jeśli nie widzisz żadnych krawędzi, wszystkie węzły, które odwiedziłeś do tej pory, są punktami artykulacji.

Potrzebujemy więc algorytmu, który odwiedza wierzchołki i zaznacza wszystkie punkty między celem tylnych krawędzi jako aktualnie odwiedzanych węzłów jak w ramach tego samego podgraphu. Oczywiście mogą być podgramy w podgrafach, więc musimy wybrać największy podgraph, jaki dotąd mieliśmy. Podgrafy te nazywane są Bi-Components. Możemy zaimplementować ten algorytm, przypisując każdemu dwuskładnikowi identyfikator, który jest inicjalizowany jako tylko liczba liczby wierzchołków, które odwiedziliśmy do tej pory. Później, gdy znajdziemy tylne krawędzie, możemy zresetować identyfikator dwuznaczny do najniższego, jaki znaleźliśmy do tej pory.

Oczywiście potrzebujemy dwóch karnetów. W pierwszym przebiegu chcemy dowiedzieć się, który wierzchołek widzimy od każdego wierzchołka przez tylne krawędzie, jeśli takie istnieją. W drugim przejściu chcemy odwiedzać wierzchołki w przeciwnym kierunku i zbierać minimalny identyfikator dwuskładnikowy (tj. Najwcześniejszy przodek dostępny od jakichkolwiek potomków). DFS oczywiście pasuje tutaj. W DFS najpierw zejdziemy na dół, a następnie wrócimy, więc oba powyższe przebiegi można wykonać w jednym przejściu DFS.

Teraz bez zbędnych ceregieli, oto pseudokod:

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