Tarjans algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. juni 2022; checks kræver 5 redigeringer .

Tarjans algoritme  er en algoritme til at finde stærkt forbundne komponenter i en digraf , der kører i lineær tid.


Denne algoritme er baseret på:

  1. Toppunkterne betragtes i omvendt topologisk rækkefølge, så i slutningen af ​​den rekursive funktion for det oprindelige toppunkt vil der ikke blive stødt på noget toppunkt fra den samme stærkt forbundne komponent, da alle toppunkter, der kan nås fra det oprindelige toppunkt, allerede er blevet behandlet.
  2. Tilbagemeldinger i et træ giver en anden vej fra et toppunkt til et andet og forbinder de stærkt forbundne komponenter til en.

Uformel beskrivelse af algoritmen

Tarjans algoritme kan forstås som en variation af dybde-først søgealgoritmen , hvor yderligere trin udføres, når en node besøges, og behandlingen af ​​noden er afsluttet. Et besøg på et vertex opstår, når man bevæger sig fra roden til bladene, og afslutningen af ​​bearbejdningen af ​​vertexet sker på vej tilbage. Når et toppunkt besøges, skubbes det ind i hjælpestakken; når en stærkt forbundet komponent behandles, skubbes alle dens toppunkter ud af denne stak [1] .

Algoritme i pseudokode

// input data: rettet graf G = (V, A) // output data: sæt af stærkt forbundne komponenter indeks  := 0 stak  := [] for hver v i V gør hvis v .index = null så strongconnect( v ) function strongconnect( v ) // I indeks gemmer vi antallet af tidligere behandlede toppunkter, v.index er "indgangstiden" til vertexet v v .index := indeks v .lowlink := indeksindeks  := indeks + 1 stak .push( v ) // OnStack-feltet er nødvendigt for at kontrollere, om toppen hører til stakken i O(1) v .onStack := true // Iterér over de buer, der udgår fra v for hver ( v , w ) i A do hvis w .index = null så // Vertex w er ikke blevet besøgt før; kør rekursivt fra den strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) ellers hvis w .onStack så // Vertex w er på stakken, så den hører til den samme stærkt forbundne komponent som v / / Hvis w ikke er på stakken, så fører buen ( v , w ) til den tidligere behandlede stærkt forbundne komponent og bør ignoreres // Bemærk: den næste linje bruger bevidst w.index i stedet for w.lowlink - dette refererer til Tarjans originale artikel / / Hvis vi erstatter w.index med w.lowlink, forbliver algoritmen korrekt v .lowlink := min( v .lowlink, w .index) // Vertex v er roden af ​​den nuværende stærkt forbundne komponent, alle toppunkter i stakken fra v og derover danner denne komponent, hvis v .lowlink = v .index så oprette en ny stærkt forbundet komponent gentag w  := stak .pop() w .onStack := falsk tilføj w til den nuværende stærkt tilsluttede komponent, mens w ≠ v udsende den nuværende stærkt tilsluttede komponent

Åbningstider

Algoritmen har tidskompleksitet , hvor  er antallet af buer og  er grafens toppunkter [1] .

Se også

The Strongly Connected Two-Stack Component Search Algoritme  er en lignende algoritme, der bruger dybde-først-søgning.

Noter

  1. ↑ 1 2 Jeremy Sik et al., 2006 .

Links

Litteratur