DFS, rekursio ja iteratiiviset pinot
Tutki syvälle ja vältä rekursion rajoitukset
DFS, rekursio ja iteratiiviset pinot on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.
Mitä DFS tekee
DFS etenee yhtä reittiä pitkin niin syvälle kuin mahdollista, palaa sitten taaksepäin ja kokeilee seuraavaa reittiä. Ajatelkaa, että tutkisitte sokkeloa käytävä kerrallaan. 🧭
DFS ja BFS
BFS leviää kehittäin, kun taas DFS etenee ensin syvälle. Molemmat käyvät kaikissa saavutettavissa olevissa solmuissa, mutta hyvin erilaisessa järjestyksessä.
Rekursiivinen rakenne
Rekursiivinen DFS merkitsee solmun visited-tilaan ja kutsuu sitten itseään jokaiselle käsittelemättömälle naapurille. Kutsupino muistaa, mihin on palattava.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Merkitkää ennen rekursiota
Asettakaa visited, kun saavutte solmuun, ennen naapureiden tutkimista. Muuten syklit johtavat DFS:n loputtomaan rekursioon.
Rekursiorajan ansa
Python rajoittaa rekursion lähes 1 000 kutsuun. Syvä graafi aiheuttaa RecursionError-virheen, joka näkyy ajonaikaisena virheenä.
Nostakaa raja
Yksi nopea korjaus on nostaa raja setrecursionlimit-funktion avulla. Asettakaa se suurinta mahdollista syvyyttä suuremmaksi ennen DFS:n suorittamista.
import sys
sys.setrecursionlimit(300000)Käyttäkää sen sijaan iteroivaa ratkaisua
Turvallisin korjaus on toteuttaa iteratiivinen DFS oman pinon avulla. Kun kutsusyvyydellä ei ole merkitystä, rekursio ei voi koskaan kaatua.
stack = [start]Poimikaa pinosta
Poimikaa jokaisella kierroksella pinon päällimmäinen alkio. Viimeisenä sisään, ensimmäisenä ulos -periaate vie DFS:n ensin viimeisimpänä avatulle reitille.
u = stack.pop()Lisätkää naapurit pinoon
Kun olette poimineet solmun u, lisätkää jokainen käsittelemätön naapuri pinoon. Merkitkää ne, jotta niitä ei lisätä uudelleen.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Iteratiivinen silmukka kokonaisuudessaan
Toistakaa poimimista ja lisäämistä niin kauan kuin pinossa on solmuja. Kun pino tyhjenee, olette käyneet kaikissa saavutettavissa olevissa solmuissa.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Sama kustannus kuin BFS:llä
DFS käy BFS:n tavoin jokaisessa solmussa ja kaaressa kerran, joten sen aikavaativuus on O(n + m). Valitkaa menetelmä sen mukaan, kumpi etenemisjärjestys sopii tehtävään.
Pikatarkistus
Rekursiivinen DFS kaatuu syvässä graafissa. Miksi?
Kertaus
Suoritatte DFS:n joko rekursiivisesti tai oman pinon avulla, merkitsette solmun käsitellyksi siihen saavuttaessa ja vaihdatte iteratiiviseen versioon, kun graafi on syvä. 🎉
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 ”DFS, rekursio ja iteratiiviset pinot” ilmainen?
Kyllä – oppitunnin ”DFS, rekursio ja iteratiiviset pinot” 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 ”DFS, rekursio ja iteratiiviset pinot”?
Tutki syvälle ja vältä rekursion rajoitukset 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 3/4.
Kuinka kauan ”DFS, rekursio ja iteratiiviset pinot”-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
- Vieryslistat syötteestä
- BFS painottamattomien polkujen lyhimmille reiteille
- DFS, rekursio ja iteratiiviset pinot
- Yhtenäiset komponentit ja flood fill