Upptäck cykler i riktade grafer
Färglägg noder för att hitta bakkanter
Upptäck cykler i riktade grafer är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Varför cykler spelar roll
En riktad cykel innebär att beroenden leder tillbaka till sig själva. Om du hittar en sådan vet du att ingen topologisk ordning eller giltig schemaläggning kan finnas.
Oriktade grafer fungerar annorlunda
Cykeldetektering här handlar om riktning. Att följa kanter åt fel håll räknas inte, så metoder för oriktade grafer kan inte användas.
Tanken bakom tre färger
Ge varje nod en av tre färger: vit betyder obesökt, grå betyder att den bearbetas och svart betyder att den är helt klar.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGrå betyder att noden finns på stacken
En grå nod finns på din aktuella DFS-sökväg. Du har gått in i den men ännu inte utforskat alla dess efterkommande noder.
Gå in i en nod
När DFS når en nod färgar du den grå innan du utforskar den. Då markeras den som en del av den aktiva sökvägen.
def dfs(u):
color[u] = GRAYSignalen från en bakåtkant
Om du når en granne som redan är grå har du hittat en bakåtkant till den aktuella sökvägen. Det är en cykel.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleGör rekursion på vita noder
En vit granne är ny, så gör rekursion på den. För tillbaka True så snart något djupare anrop rapporterar en cykel.
elif color[v] == WHITE and dfs(v):
return TrueSvart betyder säker
En svart granne är helt utforskad och fri från cykler, så du kan ignorera den. Att besöka den igen skulle bara slösa tid.
Slutför en nod
När alla grannar har hanterats färgar du noden svart. Den lämnar den aktiva sökvägen och markeras som färdig.
color[u] = BLACK
return FalseTäck alla komponenter
Grafen kan vara osammanhängande, så starta DFS från varje nod som fortfarande är vit för att vara säker på att hela grafen kontrolleras.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Tänk på rekursionsgränsen
Djupa grafer kan överskrida Pythons rekursionsstack. Höj gränsen eller skriv om DFS med en explicit stack.
import sys
sys.setrecursionlimit(300000)Snabb kontroll
Under DFS når du en granne som för närvarande är grå. Vad har du just hittat?
Sammanfattning: Cykeldetektering
Färga noderna vita, grå och sedan svarta. En grå granne under DFS är en bakåtkant, vilket bevisar att det finns en riktad cykel. 🔁
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Upptäck cykler i riktade grafer” gratis?
Ja – hela texten till ”Upptäck cykler i riktade grafer” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Upptäck cykler i riktade grafer”?
Färglägg noder för att hitta bakkanter Ni övar på Competitive Programming Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Upptäck cykler i riktade grafer”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Topologisk sortering med Kahns algoritm
- Upptäck cykler i riktade grafer
- Starkt sammanhängande komponenter
- Broar och artikulationspunkter