Adjacency-lister fra input
Byg den graf, som konkurrencerne giver dig
Adjacency-lister fra input er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 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 Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad en graf egentlig er
En graf er blot prikker, der kaldes knudepunkter, forbundet af linjer, der kaldes kanter. Byer forbundet af veje er en graf, du allerede kender. 🗺️
Knudepunkter og kanter
Hvert knudepunkt er en ting, og hver kant angiver, at to knudepunkter er forbundet. Grafer i konkurrencer nummererer normalt knudepunkterne fra 1 til n.
Naboskabslisten
Den foretrukne lagring i konkurrencer er en naboskabsliste: Gem en liste over de direkte naboer for hvert knudepunkt.
adj = [[] for _ in range(n + 1)]Hvorfor ikke en matrix
En matrix bruger n i anden hukommelse, hvilket eksploderer for store n. En naboskabsliste gemmer kun kanter, der findes, så den skalerer bedre.
Læs den første linje
De fleste input begynder med to tal: n knudepunkter og m kanter. Læs dem først, så du ved, hvor mange kanter du kan forvente.
n, m = map(int, input().split())Én kant pr. linje
Hver af de næste m linjer angiver et par u v. Den ene kant betyder, at u og v er direkte forbundet.
u, v = map(int, input().split())Ikke-rettet betyder begge veje
For en ikke-rettet kant skal du tilføje forbindelsen i begge retninger. Du kan gå fra u til v og fra v til u.
adj[u].append(v)
adj[v].append(u)Rettet betyder én vej
For en rettet kant skal du kun gemme forbindelsen fra u til v. Læs opgaveteksten grundigt for at vide, hvilken type du har.
adj[u].append(v)Byg den i en løkke
Kør en løkke m gange, læs hvert par, og udfyld listerne. Når løkken er færdig, indeholder din naboskabsliste hele grafen.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indeksering fra 1 eller fra 0
Hvis knudepunkterne starter ved 1, skal du dimensionere din liste til n plus 1, så indeks n er gyldigt. Forveksling af indekseringen giver fejl, der kan være svære at opdage.
Besøg et knudepunkts naboer
Når grafen er bygget, er det nemt at udforske den: Gennemgå adj for et knudepunkt for at nå hver nabo i ét trin.
for nb in adj[u]:
print(nb)Hurtigt tjek
Du læser en ikke-rettet kant u v. Hvad gemmer du?
Opsummering
Du kan nu bygge en graf som en naboskabsliste: læse n og m, gennemgå kanterne og tilføje begge retninger, når grafen ikke er rettet. 🎉
Lær Forberedelse til kodeinterviews 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
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Adjacency-lister fra input” gratis?
Ja — hele teksten til “Adjacency-lister fra input” 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 Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Adjacency-lister fra input”?
Byg den graf, som konkurrencerne giver dig Du øver dig i Forberedelse til kodeinterviews 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å Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews 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 1 af 4.
Hvor lang tid tager lektionen “Adjacency-lister fra input”?
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 Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-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
- Adjacency-lister fra input
- BFS for korteste uvægtede stier
- DFS, rekursion og iterative stacks
- Sammenhængende komponenter og flood fill