Topologinen järjestäminen Kahnin algoritmilla
Järjestä tehtävät, jotka riippuvat toisistaan
Topologinen järjestäminen Kahnin algoritmilla on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/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 Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mikä topologinen järjestys on
Topologinen järjestys luettelee suunnatun graafin kaikki solmut niin, että jokainen kaari kulkee aikaisemmasta solmusta myöhempään. Ajattele tehtäviä ennen tehtäviä, jotka tarvitsevat niitä.
Vain DAGit sallitaan
Tämä toimii vain DAGissa, eli suunnatussa syklittömässä graafissa. Jos graafissa on sykli, mikään kelvollinen järjestys ei voi täyttää kaikkia riippuvuuksia.
Sisäasteen idea
Kahnin algoritmi perustuu sisäasteeseen: se kertoo, kuinka monta kaarta osoittaa solmuun. Sisäasteeltaan nollan solmun riippuvuudet ovat kaikki täytetty.
Laske jokainen sisäaste
Ensimmäisellä kierroksella käy kaikki kaaret läpi ja laske, kuinka monta kertaa kukin solmu esiintyy kohdesolmuna. Näin saat jokaisen solmun sisäasteen.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Alusta valmiiden jono
Jokainen solmu, jonka sisäaste on nolla, on heti valmis, joten lisää ne kaikki jonoon aloitusta varten.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Käsittele yksi solmu
Poista valmis solmu jonosta ja lisää se järjestykseesi. Sen voi nyt käsitellä turvallisesti, koska kaikki sen riippuvuudet on täytetty.
u = q.popleft()
order.append(u)Vapauta sen naapurit
Vähennä jokaisen naapurin sisäastetta yhdellä. Kun naapurin arvo saavuttaa nollan, se on valmis ja liittyy jonoon.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Toista, kunnes jono on tyhjä
Jatka solmujen poistamista ja naapureiden vapauttamista, kunnes jono tyhjenee. Järjestys kasvaa yksi turvallinen solmu kerrallaan, kunnes kaikki solmut on sijoitettu.
Havaitse sykli samalla
Jos lopullisessa järjestyksessä on alle n solmua, sykli esti loput solmut. Kahnin algoritmi tarjoaa syklien tunnistuksen ilman lisäkustannuksia.
if len(order) < n:
print('cycle exists')Suoritusaika
Jokainen solmu ja kaari käsitellään kerran, joten Kahnin algoritmin aikavaativuus on O(V + E). Se skaalautuu miljoonien kaarten graafeihin.
Monta kelvollista järjestystä
Kun useita solmuja on valmiina yhtä aikaa, mikä tahansa niistä voidaan käsitellä seuraavaksi. Siksi DAGilla on usein monta kelvollista topologista järjestystä, ei vain yhtä.
Pikatarkistus
Suoritat Kahnin algoritmin loppuun, mutta järjestyksessä on alle n solmua. Mitä se tarkoittaa?
Kertaus: Kahnin algoritmi
Laske sisäasteet, lisää nollat jonoon, poista solmu, vähennä naapureiden arvoja ja toista. Näin saat siistin topologisen lajittelun ajassa O(V+E). 🚀
Opi Python 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
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Topologinen järjestäminen Kahnin algoritmilla” ilmainen?
Kyllä – oppitunnin ”Topologinen järjestäminen Kahnin algoritmilla” 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 Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Topologinen järjestäminen Kahnin algoritmilla”?
Järjestä tehtävät, jotka riippuvat toisistaan Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Topologinen järjestäminen Kahnin algoritmilla”-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ä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-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
- Topologinen järjestäminen Kahnin algoritmilla
- Syklien tunnistaminen suunnatuista graafeista
- Vahvasti yhtenäiset komponentit
- Sillat ja leikkauspisteet