Tarjans algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 juni 2022; kontroller kräver 5 redigeringar .

Tarjans algoritm  är en algoritm för att hitta starkt sammankopplade komponenter i en digraf som går i linjär tid.


Denna algoritm är baserad på:

  1. Hörnena betraktas i omvänd topologisk ordning, så i slutet av den rekursiva funktionen för den ursprungliga vertexen kommer ingen vertex från samma starkt sammankopplade komponent att påträffas, eftersom alla hörn som kan nås från den ursprungliga vertexen redan har bearbetats.
  2. Återkopplingar i ett träd ger en andra väg från en vertex till en annan och kopplar samman de starkt anslutna komponenterna till en.

Informell beskrivning av algoritmen

Tarjans algoritm kan förstås som en variant av sökalgoritmen djup-först , där ytterligare steg utförs när en nod besöks och bearbetningen av noden är klar. Ett besök på ett vertex inträffar när man flyttar från roten till bladen, och slutet av bearbetningen av vertexet inträffar på vägen tillbaka. När en vertex besöks skjuts den in i hjälpstacken, när en starkt ansluten komponent bearbetas skjuts alla dess hörn ut ur denna stapel [1] .

Algoritm i pseudokod

// indata: riktad graf G = (V, A) // utdata: uppsättning av starkt anslutna komponenter index  := 0 stack  := [] för varje v i V gör om v .index = null då strongconnect( v ) function strongconnect( v ) // I index lagrar vi antalet tidigare bearbetade hörn, v.index är "inträdestiden" till vertex v v .index := index v .lowlink := index index  := index + 1 stack .push( v ) // OnStack-fältet behövs för att kontrollera om toppen tillhör stacken i O(1) v .onStack := true // Iterera över bågarna som utgår från v för varje ( v , w ) i A gör om w .index = null då // Vertex w har inte besökts tidigare; kör rekursivt från den strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) annars om w .onStack då // Vertex w är på stacken, så den tillhör samma starkt anslutna komponent som v / / Om w inte finns på stacken, så leder bågen ( v , w ) till den tidigare bearbetade starkt anslutna komponenten och bör ignoreras // Notera: nästa rad använder medvetet w.index istället för w.lowlink - detta hänvisar till Tarjans originalartikel / / Om vi ​​ersätter w.index med w.lowlink, förblir algoritmen korrekt v .lowlink := min( v .lowlink, w .index) // Vertex v är roten till den nuvarande starkt anslutna komponenten, alla hörn i stacken från v och uppåt bildar denna komponent om v .lowlink = v .index då skapa en ny starkt ansluten komponent upprepa w  := stack .pop() w .onStack := false lägg till w till den nuvarande starkt anslutna komponenten medan w ≠ v mata ut den ström starkt anslutna komponenten

Öppettider

Algoritmen har tidskomplexitet , där  är antalet bågar och  är grafens hörn [1] .

Se även

Strongly Connected Two-Stack Component Search Algoritm  är en liknande algoritm som använder djup-först-sökning.

Anteckningar

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

Länkar

Litteratur