Tarjanin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14.6.2022 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Tarjanin algoritmi  on algoritmi vahvasti toisiinsa liittyvien komponenttien löytämiseksi lineaarisessa ajassa juoksevasta digraafista .


Tämä algoritmi perustuu:

  1. Pörssejä tarkastellaan käänteisessä topologisessa järjestyksessä, joten alkuperäisen kärjen rekursiivisen funktion lopussa ei kohtaa yhtään kärkeä samasta vahvasti kytketystä komponentista, koska kaikki alkuperäisestä kärjestä saavutettavat pisteet on jo käsitelty.
  2. Palautteet puussa antavat toisen polun kärjestä toiseen ja yhdistävät vahvasti toisiinsa liittyvät komponentit yhdeksi.

Algoritmin epävirallinen kuvaus

Tarjanin algoritmi voidaan ymmärtää muunnelmana syvyys-first- hakualgoritmista , jossa suoritetaan lisävaiheita, kun solmussa käydään ja solmun käsittely on valmis. Kärkipisteessä käynti tapahtuu siirryttäessä juuresta lehtiin, ja kärjen käsittely päättyy paluumatkalla. Kun pisteessä käydään, se työnnetään apupinoon, kun vahvasti kytketty komponentti käsitellään, kaikki sen kärjet työnnetään ulos tästä pinosta [1] .

Algoritmi pseudokoodissa

// tulotiedot: suunnattu graafi G = (V, A) // lähtötiedot: joukko vahvasti kytkettyjä komponentteja index  := 0 pino  := [] jokaiselle v :lle V do jos v .index = null , sitten strongconnect( v ) funktio strongconnect( v ) // Indeksiin tallennetaan aiemmin käsiteltyjen kärkien lukumäärä, v.index on "sisääntuloaika" kärkeen v v .index := indeksi v .lowlink := indeksiindeksi  := indeksi + 1 pino .push( v ) // OnStack-kenttää tarvitaan tarkistamaan, kuuluuko yläosa pinoon O(1) v .onStack := true // Iteroi v:stä lähtevien kaarien yli jokaiselle ( v , w ) :lle A do , jos w .index = null then // Vertexissä w ei ole vieraillut aiemmin; ajaa siitä rekursiivisesti strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) muuten jos w .onStack sitten // Vertex w on pinossa, joten se kuuluu samaan vahvasti yhdistettyyn komponenttiin kuin v / / Jos w ei ole pinossa, kaari ( v , w ) johtaa aiemmin käsiteltyyn vahvasti yhdistettyyn komponenttiin ja se tulee jättää huomiotta // Huomautus: seuraavalla rivillä käytetään tarkoituksella w.indexiä w.lowlinkin sijaan - tämä viittaa Tarjanin alkuperäinen artikkeli / / Jos w.index korvataan w.lowlinkillä, algoritmi pysyy oikeana v .lowlink := min( v .lowlink, w .index) // Vertex v on nykyisen vahvasti kytketyn komponentin juuri, kaikki pinon kärjet v:stä ja ylemmistä muodostavat tämän komponentin, jos v .lowlink = v .index luoda uusi vahvasti yhdistetty komponentti toista w  := pino .pop() w .onStack := false lisää w nykyiseen vahvasti kytkettyyn komponenttiin, kun w ≠ v lähettää nykyisen vahvasti kytketyn komponentin

Aukioloajat

Algoritmilla on aikamonimutkaisuus , jossa  on kaarien lukumäärä ja  ovat graafin kärjet [1] .

Katso myös

Strongly Connected Two-Stack Component Search Algorithm  on samanlainen algoritmi, joka käyttää syvällistä hakua.

Muistiinpanot

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

Linkit

Kirjallisuus