Vahvasti yhtenäiset komponentit Kosarajulla
Suorittakaa DFS alkuperäisessä graafissa suoritusjärjestyksen saamiseksi, muodostakaa käänteisgraafi ja suorittakaa DFS uudelleen käänteisessä suoritusjärjestyksessä SCC-komponenttien tunnistamiseksi.
Vahvasti yhtenäiset komponentit Kosarajulla on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Vahvasti yhtenäiset komponentit
Suunnatun graafin vahvasti yhtenäinen komponentti (SCC) on solmujen maksimaalinen joukko, jossa jokaisesta solmusta on polku jokaiseen muuhun joukon solmuun. Jos esimerkiksi solmut A, B ja C muodostavat syklin (A→B→C→A), ne kaikki kuuluvat samaan SCC:hen. Yksittäinen solmu, jolla ei ole silmukkaa itseensä, muodostaa oman SCC:nsä. SCC:t paljastavat suunnatun graafin syklisen rakenteen.
Kosarajun algoritmi: kaksi DFS-kierrosta
Kosarajun algoritmi löytää kaikki SCC:t aikavaativuudella O(V + E) käyttämällä kahta DFS-kierrosta. Kierros 1: suorita DFS alkuperäisellä graafilla ja lisää solmut pinoon niiden valmistumisjärjestyksessä eli jälkijärjestyksessä. Kierros 2: suorita DFS transponoidulla eli käännetyllä graafilla käsitellen solmut käänteisessä valmistumisjärjestyksessä eli poistamalla ne pinosta. Jokainen kierroksen 2 DFS-puu muodostaa yhden SCC:n.
Miksi Kosaraju toimii
Kierroksella 1 se SCC, jonka DFS-puu valmistuu viimeisenä, on komponentti-DAGin SCC, jolla ei ole lähteviä reunoja muihin SCC:ihin eli niin sanottu ”nielu”-SCC. Transponoidussa graafissa tällä SCC:llä ei ole muista SCC:istä tulevia reunoja, joten siitä aloitettu DFS pysyy kyseisen SCC:n sisällä kierroksella 2. Jokainen seuraava kierroksen 2 DFS pysyy omassa SCC:ssään, koska kaikki komponenttien väliset reunat käännettiin ja ne johtavat jo vierailtuihin SCC:ihin.
Kierros 1: valmistumisjärjestyksen muodostaminen
Suorita DFS alkuperäisellä graafilla ja lisää jokainen solmu pinoon sen käsittelyn päätyttyä eli jälkijärjestyksessä. Tällä kierroksella komponenttien tunnistamisella ei ole väliä — tarvitsemme vain valmistumisjärjestyksen. Viimeisenä valmistuva solmu kuuluu komponentti-DAGin ”lähde”-SCC:hen.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphKierros 2: DFS transponoidulla graafilla
Poista solmut valmistumispinosta suurimmasta valmistumisajasta alkaen ja suorita DFS transponoidulla graafilla. Jokainen käymättömästä solmusta aloitettu DFS löytää täsmälleen yhden SCC:n. Merkitse kaikki tämän DFS:n saavuttamat solmut samaan komponenttiin kuuluviksi.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarGraafin transponointi
Transponoitu graafi kääntää jokaisen reunan suunnan: jos alkuperäisessä graafissa on u → v, transponoidussa graafissa on v → u. Transponointi säilyttää SCC:t — jos A ja B kuuluvat samaan SCC:hen alkuperäisessä graafissa, ne kuuluvat samaan SCC:hen myös transponoidussa graafissa, koska kaikki polut kääntyvät mutta yhdistävät solmut edelleen. Transponoidun graafin muodostaminen syötettä luettaessa, kuten edellä, välttää erillisen transponointivaiheen.
Iteratiivinen versio suurille graafeille
Suurissa graafeissa rekursiivinen DFS kannattaa korvata iteratiivisella DFS:llä, jossa käytetään eksplisiittistä pinoa Pythonin rekursiorajan välttämiseksi. Iteratiivinen versio lisää solmuja pinoon, käsittelee ne ja ylläpitää erillistä 'return'-merkintää jälkijärjestyksen simuloimiseksi.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Tarjanin algoritmi: vaihtoehtoinen SCC-menetelmä
Tarjanin algoritmi löytää SCC:t yhdellä DFS-läpikäynnillä, kun taas Kosarajun algoritmi käyttää kahta läpikäyntiä. Se ylläpitää solmupinoa ja määrittää jokaiselle solmulle löytöajan sekä low-link-arvon. Kun solmun löytöaika on sama kuin sen low-link-arvo, solmu on SCC:n juuri. Tarjanin algoritmi on hieman monimutkaisempi toteuttaa, mutta sen ansiosta käänteisgraafia ei tarvitse muodostaa. Molempien aikavaativuus on O(V + E).
SCC:iden sovellukset
SCC:itä käytetään esimerkiksi seuraavissa tarkoituksissa: (1) Kääntäjän optimointi — toisistaan riippuvien rekursiivisten funktioiden tunnistaminen. (2) Sosiaalisen verkoston analyysi — tiiviisti verkottuneiden yhteisöjen löytäminen. (3) 2-SAT-ongelma — kahden literaalin lausekkeiden toteutuvuuden määrittäminen. (4) Verkon indeksointi — tiheästi toisiinsa linkittyneiden sivuryhmien tunnistaminen. (5) Kondensaatio-DAG — SCC:iden löytämisen jälkeen graafin kondensaatio on DAG, mikä mahdollistaa syklisten graafien topologisen analyysin.
Kondensaatio-DAG
Suunnatun graafin kondensaatiossa jokainen SCC kutistetaan yhdeksi solmuksi, ja kahden supersolmun välille lisätään kaari, jos niiden muodostavien SCC:iden välillä on kaari. Tuloksena on aina DAG, jolle voidaan suorittaa topologinen järjestäminen. Näin DAG-graafeille tarkoitetut algoritmit, kuten DP, voidaan ulottaa yleisiin suunnattuihin graafeihin käsittelemällä niiden kondensaatiota.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]SCC:iden määrä ja graafin ominaisuudet
Suunnatun graafin SCC:iden määrä paljastaa sen syklisen rakenteen. DAG:ssa on n SCC:tä, koska jokainen solmu muodostaa oman SCC:nsä. Vahvasti yhtenäisessä graafissa on täsmälleen yksi SCC. Yleisesti SCC:t muodostavat kondensaation jälkeen DAG:n eli kondensaatio-DAG:n. Jos kondensaatio-DAG:lla on yksikäsitteinen lähde (solmu, jonka sisäaste on 0) ja yksikäsitteinen nielu (solmu, jonka ulkoaste on 0), tietyt yhtenäisyysominaisuudet toteutuvat. Näitä ominaisuuksia tutkitaan tehtävissä, joissa käsitellään saavutettavuutta mahdollisimman vähäisten uusien kaarien lisäämisen jälkeen.
Pikatesti
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että SCC:t ovat maksimaalisia joukkoja, joissa jokainen solmu on saavutettavissa kaikista muista solmuista, Kosarajun algoritmi käyttää kahta DFS-läpikäyntiä — ensin alkuperäisellä graafilla loppumisjärjestyksen löytämiseksi ja sitten käänteisgraafilla ja minkä tahansa suunnatun graafin kondensaatio on DAG, jota voidaan käyttää jatkoanalyysiin. Seuraavaksi rakennamme TrieNode-tietorakenteita lisäys-, haku- ja etuliitetoimintoja varten.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Vahvasti yhtenäiset komponentit Kosarajulla” ilmainen?
Kyllä – oppitunnin ”Vahvasti yhtenäiset komponentit Kosarajulla” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Vahvasti yhtenäiset komponentit Kosarajulla”?
Suorittakaa DFS alkuperäisessä graafissa suoritusjärjestyksen saamiseksi, muodostakaa käänteisgraafi ja suorittakaa DFS uudelleen käänteisessä suoritusjärjestyksessä SCC-komponenttien tunnistamiseksi. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Vahvasti yhtenäiset komponentit Kosarajulla”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Kahnin algoritmi: BFS-pohjainen topologinen järjestäminen
- DFS:n jälkijärjestykseen perustuva topologinen järjestäminen
- Course Schedule I ja II
- Vahvasti yhtenäiset komponentit Kosarajulla