Find cyklusser i rettede grafer
Farvelæg knuder for at finde tilbagekanter
Find cyklusser i rettede grafer er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Competitive Programming Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvorfor cyklusser betyder noget
En rettet cyklus betyder, at afhængighederne går tilbage til sig selv. Hvis du finder en, ved du, at ingen topologisk rækkefølge eller gyldig plan kan eksistere.
Urettede grafer er anderledes
Cyklusdetektion her handler om retningen. Det tæller ikke at følge kanter den forkerte vej, så metoder til urettede grafer kan ikke bruges.
Idéen med tre farver
Giv hver knude en af tre farver: hvid betyder ikke besøgt, grå betyder under behandling, og sort betyder helt færdig.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGrå betyder på stakken
En grå knude ligger på din aktuelle DFS-sti. Du er gået ind i den, men har endnu ikke undersøgt alle dens efterkommere.
Gå ind i en knude
Når DFS når en knude, skal du farve den grå, før du undersøger den. Så markerer du, at den er en del af den aktive sti.
def dfs(u):
color[u] = GRAYSignaler fra bagkanten
Hvis du når en nabo, der allerede er grå, har du fundet en bagkant ind i den aktuelle sti. Det er en cyklus.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleGå rekursivt ind i hvide knuder
En hvid nabo er ny, så gå rekursivt ind i den. Send True tilbage, så snart et dybere kald melder en cyklus.
elif color[v] == WHITE and dfs(v):
return TrueSort er sikkert
En sort nabo er undersøgt færdig og indeholder ingen cyklus, så du kan ignorere den. At besøge den igen ville kun spilde tid.
Afslut en knude
Når alle naboer er behandlet, skal du farve knuden sort. Den forlader den aktive sti og markeres som færdig.
color[u] = BLACK
return FalseDæk alle komponenter
Grafen kan være usammenhængende, så start DFS fra hver knude, der stadig er hvid, for at sikre, at du undersøger hele grafen.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Vær opmærksom på rekursionsgrænsen
Dybe grafer kan få Pythons rekursionsstak til at løbe over. Hæv grænsen, eller skriv DFS om med en eksplicit stak.
import sys
sys.setrecursionlimit(300000)Hurtigt tjek
Under DFS når du en nabo, der i øjeblikket er grå. Hvad har du netop fundet?
Opsummering: Cyklusdetektion
Farv knuder hvide, grå og derefter sorte. En grå nabo under DFS er en bagkant, som beviser en rettet cyklus. 🔁
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Find cyklusser i rettede grafer” gratis?
Ja — hele teksten til “Find cyklusser i rettede grafer” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Competitive Programming Academy-kurset, skal du opgradere til CoddyKit PRO. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Find cyklusser i rettede grafer”?
Farvelæg knuder for at finde tilbagekanter Du øver dig i Competitive Programming Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Competitive Programming Academy?
Der kræves ingen tidligere erfaring. Competitive Programming Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Find cyklusser i rettede grafer”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Competitive Programming Academy-lektion?
Ja. Alle Competitive Programming Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Topologisk sortering med Kahns algoritme
- Find cyklusser i rettede grafer
- Stærkt sammenhængende komponenter
- Broer og artikulationspunkter