Algoritmer til stifinding (BFS, DFS)
Undersøg algoritmer som Breadth-First Search og Depth-First Search for at finde stier og forbindelser i en graf.
Algoritmer til stifinding (BFS, DFS) er en gratis Grundlæggende om grafdatabasen Neo4j-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i Grundlæggende om grafdatabasen Neo4j, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Grundlæggende om grafdatabasen Neo4j-kurset indeholder 4 lektioner i alt.
Find vej i grafer
Grafer handler om forbindelser! Forestil dig et kort, hvor byer er punkter, og veje er linjer. At finde den bedste rute fra én by til en anden er et klassisk problem inden for "stifinding".
I denne lektion undersøger vi to grundlæggende algoritmer til at finde stier i grafer: Breath-First Search (BFS) og Depth-First Search (DFS).
Hvad er en graf? Hurtig repetition
Før vi går i gang med algoritmerne, repeterer vi kort, hvad en graf er:
- Noder: Det er entiteterne eller punkterne i din graf (f.eks. personer, byer og produkter).
- Relationer: Det er forbindelserne mellem noder (f.eks. "FRIENDS_WITH" og "LOCATED_IN").
- Sti: En række forbundne noder og relationer fra én node til en anden.
BFS: Udforskning lag for lag
Breadth-First Search (BFS) minder om at udforske en labyrint ved at undersøge alle umiddelbare udgange fra det rum, du står i, derefter alle udgange fra de rum og så videre.
Den udforsker systematisk en graf niveau for niveau og sikrer, at den finder den korteste sti målt i antallet af relationer mellem to noder (i en uvægtet graf).
Sådan fungerer BFS
BFS bruger en "kø" (ligesom en kø i en butik: først ind, først ud) til at holde styr på, hvilke noder der skal besøges som de næste.
- Den starter ved en given node.
- Den besøger først alle nodens direkte naboer.
- Derefter besøger den alle ubesøgte naboer til disse naboer.
- Den holder styr på besøgte noder for at undgå løkker og overflødigt arbejde.
Kodeeksempel med BFS
Lad os se på et enkelt Python-eksempel med BFS på en lille graf. Vi repræsenterer grafen ved hjælp af en ordbog, hvor nøglerne er noder, og værdierne er lister over deres naboer.
def bfs_path(graph, start_node):
visited = []
queue = [start_node]
visited.append(start_node)
path = []
while queue:
current_node = queue.pop(0) # Get first node
path.append(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.append(neighbor)
queue.append(neighbor)
return path
if __name__ == "__main__":
# A simple graph:
# A -- B
# | |
# C -- D
graph_data = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
print("BFS path from 'A':")
print(bfs_path(graph_data, 'A'))DFS: Gå i dybden
Depth-First Search (DFS) bruger en anden tilgang. I stedet for at udforske lag for lag går den så dybt som muligt langs hver gren, før den går tilbage.
Tænk på det som at bevæge sig gennem en labyrint ved altid at vælge én sti og følge den til enden. Hvis det er en blindgyde, går du tilbage og prøver en anden sti.
Sådan fungerer DFS
DFS bruger typisk en "stak" (sidst ind, først ud) eller rekursion til at styre sin udforskning.
- Den starter ved en given node.
- Den vælger én ubesøgt nabo og går til den.
- Den gentager processen og bevæger sig dybere ind i grafen.
- Hvis den når en blindgyde eller en besøgt node, går den tilbage til den seneste node med ubesøgte naboer.
Kodeeksempel med DFS
Her er et Python-eksempel med DFS. Vi bruger en rekursiv tilgang, som naturligt bruger kaldestakken til at opnå gennemløb i dybden.
def dfs_path(graph, start_node, visited=None, path=None):
if visited is None:
visited = set()
if path is None:
path = []
visited.add(start_node)
path.append(start_node)
for neighbor in graph[start_node]:
if neighbor not in visited:
dfs_path(graph, neighbor, visited, path)
return path
if __name__ == "__main__":
# A simple graph:
# A -- B
# | |
# C -- D
graph_data = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
print("DFS path from 'A':")
# Note: DFS path can vary based on neighbor order
print(dfs_path(graph_data, 'A'))BFS kontra DFS: Vigtige forskelle
BFS og DFS er begge effektive, men de egner sig til forskellige problemer:
- BFS: Garanterer den korteste sti (målt i relationer). Er god til at finde de nærmeste venner eller placeringer.
- DFS: Er nyttig til at kontrollere forbindelser, finde alle stier eller udføre topologisk sortering. Kan bruge mindre hukommelse i meget dybe grafer.
- Hukommelse: BFS kan bruge mere hukommelse i brede grafer (med mange naboer). DFS kan bruge mere stakplads i dybe grafer.
Hurtigt tjek: Valg af stifindingsalgoritme
Du bygger en funktion til et socialt netværk, som skal finde den korteste forbindelse (færrest venner) mellem to brugere. Hvilken algoritme egner sig bedst til denne opgave i en uvægtet graf?
Opsummering og næste trin
Godt gået! I denne lektion har du lært om de to grundlæggende algoritmer til gennemløb af grafer:
- Breadth-First Search (BFS): Udforsker lag for lag og er god til at finde korteste stier.
- Depth-First Search (DFS): Går i dybden og er nyttig til at kontrollere forbindelser eller finde alle stier.
Det er afgørende at forstå disse algoritmer, hvis du vil løse mange grafproblemer, og det hjælper dig med at forstå, hvordan grafdatabaser effektivt finder forbindelser.
Lær Grundlæggende om grafdatabasen Neo4j 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
- 12
- Lektioner
- 48
Ofte stillede spørgsmål
Er lektionen “Algoritmer til stifinding (BFS, DFS)” gratis?
Ja — alle 3 lektioner i læringssporet Grundlæggende om grafdatabasen Neo4j, inklusive “Algoritmer til stifinding (BFS, DFS)”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Grundlæggende om grafdatabasen Neo4j-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Algoritmer til stifinding (BFS, DFS)”?
Undersøg algoritmer som Breadth-First Search og Depth-First Search for at finde stier og forbindelser i en graf. Du øver dig i Grundlæggende om grafdatabasen Neo4j 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å Grundlæggende om grafdatabasen Neo4j?
Der kræves ingen tidligere erfaring. Grundlæggende om grafdatabasen Neo4j 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 “Algoritmer til stifinding (BFS, DFS)”?
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 Grundlæggende om grafdatabasen Neo4j-lektion?
Ja. Alle Grundlæggende om grafdatabasen Neo4j-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
- Algoritmer til stifinding (BFS, DFS)
- Centralitetsalgoritmer (PageRank)
- Algoritmer til fællesskabsdetektion
- Algoritmer til lighed og forudsigelse af forbindelser