Syklien tunnistaminen suunnatuista graafeista
Väritä solmut takaisinkaarien löytämiseksi
Syklien tunnistaminen suunnatuista graafeista on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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.
Miksi sykleillä on väliä
Suunnattu sykli tarkoittaa, että riippuvuudet palaavat takaisin itseensä. Sen havaitseminen kertoo, ettei topologista järjestystä tai kelvollista aikataulua voi muodostaa.
Suunnattomissa graafeissa asia on eri
Syklien tunnistuksessa on tässä kyse suunnasta. Kaaren seuraaminen väärään suuntaan ei kelpaa, joten suunnattomien graafien niksit eivät päde.
Kolmen värin idea
Anna jokaiselle solmulle yksi kolmesta väristä: valkoinen tarkoittaa käymätöntä, harmaa käsittelyssä olevaa ja musta kokonaan käsiteltyä.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nHarmaa tarkoittaa pinossa olevaa
Harmaa solmu on nykyisellä DFS-polullasi. Olet saapunut siihen, mutta et ole vielä käsitellyt kaikkia sen jälkeläisiä.
Siirry solmuun
Kun DFS saavuttaa solmun, merkitse se harmaaksi ennen tutkimista. Näin se merkitään aktiivisen polun osaksi.
def dfs(u):
color[u] = GRAYTakakaaren merkki
Jos saavutat naapurin, joka on jo harmaa, löysit takakaaren nykyiselle polulle. Se tarkoittaa sykliä.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleKutsu rekursio valkoiseen solmuun
Valkoinen naapuri on vielä tutkimaton, joten kutsu siihen rekursio. Palauta True heti, kun jokin syvempi kutsu ilmoittaa syklistä.
elif color[v] == WHITE and dfs(v):
return TrueMusta on turvallinen
Musta naapuri on tutkittu kokonaan eikä sisällä sykliä, joten voit ohittaa sen. Sen tutkiminen uudelleen vain tuhlaisi aikaa.
Viimeistele solmu
Kun kaikki naapurit on käsitelty, merkitse solmu mustaksi. Se poistuu aktiiviselta polulta ja merkitään valmiiksi.
color[u] = BLACK
return FalseKäsittele kaikki komponentit
Graafi voi olla epäyhtenäinen, joten aloita DFS jokaisesta yhä valkoisesta solmusta varmistaaksesi, että koko graafi tarkistetaan.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Huomioi rekursion raja
Syvät graafit voivat täyttää Pythonin rekursiopinon. Kasvata rajaa tai kirjoita DFS uudelleen käyttämällä eksplisiittistä pinoa.
import sys
sys.setrecursionlimit(300000)Pikatarkistus
Saavutat DFS:n aikana naapurin, joka on parhaillaan harmaa. Mitä juuri löysit?
Kertaus: syklien tunnistus
Väritä solmut ensin valkoisiksi, sitten harmaiksi ja lopuksi mustiksi. Harmaa naapuri DFS:n aikana on takakaari, joka todistaa suunnatun syklin olemassaolon. 🔁
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 ”Syklien tunnistaminen suunnatuista graafeista” ilmainen?
Kyllä – oppitunnin ”Syklien tunnistaminen suunnatuista graafeista” 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 ”Syklien tunnistaminen suunnatuista graafeista”?
Väritä solmut takaisinkaarien löytämiseksi 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 2/4.
Kuinka kauan ”Syklien tunnistaminen suunnatuista graafeista”-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
- Topologinen järjestäminen Kahnin algoritmilla
- Syklien tunnistaminen suunnatuista graafeista
- Vahvasti yhtenäiset komponentit
- Sillat ja leikkauspisteet