Adjacentielijsten uit invoer
De graaf opbouwen die wedstrijden u geven
Adjacentielijsten uit invoer is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat een graaf echt is
Een graaf bestaat uit punten, knooppunten genoemd, die met lijnen, kanten genoemd, zijn verbonden. Steden die met wegen verbonden zijn vormen een graaf die je al kent. 🗺️
Knooppunten en kanten
Elk knooppunt stelt iets voor en elke kant geeft aan dat twee knooppunten verbonden zijn. In programmeerwedstrijden worden knooppunten meestal genummerd van 1 tot n.
De adjacentielijst
De standaardopslag voor grafen in programmeerwedstrijden is een adjacentielijst: houd voor elk knooppunt een lijst met zijn directe buren bij.
adj = [[] for _ in range(n + 1)]Waarom geen matrix
Een matrix gebruikt n kwadraat aan geheugen, wat bij grote n snel explodeert. Een adjacentielijst slaat alleen bestaande kanten op en schaalt daardoor goed.
De eerste regel lezen
De meeste invoer begint met twee getallen: n knooppunten en m kanten. Lees ze eerst, zodat je weet hoeveel kanten je kunt verwachten.
n, m = map(int, input().split())Eén kant per regel
Elk van de volgende m regels bevat een paar u v. Die ene kant betekent dat u en v rechtstreeks met elkaar verbonden zijn.
u, v = map(int, input().split())Ongericht betekent beide richtingen
Voeg bij een ongerichte kant de verbinding in beide richtingen toe. Je kunt van u naar v en van v naar u lopen.
adj[u].append(v)
adj[v].append(u)Gericht betekent één richting
Sla bij een gerichte kant alleen de verbinding van u naar v op. Lees de opgave zorgvuldig om te weten welk type je hebt.
adj[u].append(v)In een lus opbouwen
Herhaal de lus m keer, lees elk paar en vul de lijsten. Na de lus bevat je adjacentielijst de hele graaf.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indexering vanaf 1 versus vanaf 0
Als knooppunten bij 1 beginnen, maak je de lijst n plus 1 groot, zodat index n geldig is. Het verwisselen van indexering veroorzaakt onopgemerkte fouten.
De buren van een knooppunt bezoeken
Als de graaf eenmaal is opgebouwd, is verkennen eenvoudig: loop over adj van een knooppunt om elke buur in één stap te bereiken.
for nb in adj[u]:
print(nb)Korte controle
Je leest een ongerichte kant u v. Wat sla je op?
Samenvatting
Je bouwt nu een graaf als adjacentielijst: lees n en m, doorloop de kanten en voeg beide richtingen toe als de graaf ongericht is. 🎉
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Adjacentielijsten uit invoer” gratis?
Ja — de volledige tekst van “Adjacentielijsten uit invoer” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Adjacentielijsten uit invoer”?
De graaf opbouwen die wedstrijden u geven Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Adjacentielijsten uit invoer”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Adjacentielijsten uit invoer
- BFS voor kortste ongewogen paden
- DFS, recursie en iteratieve stacks
- Samenhangende componenten en flood fill