Algoritmer för vägsökning (BFS, DFS)
Utforska algoritmer som bredden-först-sökning och djupet-först-sökning för att hitta vägar och kopplingar i en graf.
Algoritmer för vägsökning (BFS, DFS) är en gratis lektion i Grunderna i Neo4j-grafdatabaser på CoddyKit. Detta är lektion 1 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för Grunderna i Neo4j-grafdatabaser, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Grunderna i Neo4j-grafdatabaser innehåller totalt 4 lektioner.
Hitta vägen i grafer
Grafer handlar om kopplingar! Föreställ dig en karta där städer är punkter och vägar är linjer. Att hitta den bästa rutten från en stad till en annan är ett klassiskt problem inom "vägsökning".
I den här lektionen utforskar vi två grundläggande algoritmer för att hitta vägar i grafer: Breadth-First Search (BFS) och Depth-First Search (DFS).
Vad är en graf? Snabbrepetition
Innan vi går igenom algoritmerna repeterar vi snabbt vad en graf är:
- Noder: Entiteterna eller punkterna i din graf (till exempel personer, städer och produkter).
- Relationer: Kopplingarna mellan noder (till exempel "FRIENDS_WITH" och "LOCATED_IN").
- Väg: En sekvens av anslutna noder och relationer från en nod till en annan.
BFS: Utforska lager för lager
Breadth-First Search (BFS) är som att utforska en labyrint genom att kontrollera alla direkta utgångar från rummet du befinner dig i, sedan alla utgångar från dessa rum och så vidare.
Algoritmen utforskar systematiskt en graf nivå för nivå och hittar därmed den kortaste vägen räknat i antalet relationer mellan två noder (i en oviktad graf).
Så fungerar BFS
BFS använder en "kö" (som en kö i en butik: först in, först ut) för att hålla reda på vilka noder som ska besökas härnäst.
- Den börjar vid en given nod.
- Den besöker först alla nodens direkta grannar.
- Sedan besöker den alla obesökta grannar till dessa grannar.
- Den håller reda på besökta noder för att undvika loopar och onödigt arbete.
Kodexempel med BFS
Vi tittar på ett enkelt Python-exempel med BFS på en liten graf. Vi representerar grafen med en ordlista där nycklarna är noder och värdena är listor med deras grannar.
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å på djupet
Depth-First Search (DFS) använder en annan strategi. I stället för att utforska lager för lager går den så djupt som möjligt längs varje gren innan den backtrackar.
Tänk på det som att navigera i en labyrint genom att alltid välja en väg och följa den till slutet. Om vägen tar slut backtrackar du och provar en annan väg.
Så fungerar DFS
DFS använder vanligtvis en "stack" (sist in, först ut) eller rekursion för att hantera utforskningen.
- Den börjar vid en given nod.
- Den väljer en obesökt granne och går till den.
- Den upprepar processen och går allt djupare in i grafen.
- Om den når en återvändsgränd eller en besökt nod backtrackar den till den senaste noden med obesökta grannar.
Kodexempel med DFS
Här är ett Python-exempel med DFS. Vi använder en rekursiv metod, som naturligt utnyttjar anropsstacken för att genomföra en djup-först-genomgång.
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 jämfört med DFS: viktiga skillnader
BFS och DFS är båda kraftfulla, men de passar för olika problem:
- BFS: Garanterar den kortaste vägen (räknat i relationer). Utmärkt för att hitta de närmaste vännerna eller platserna.
- DFS: Användbar för att kontrollera konnektivitet, hitta alla vägar eller utföra topologisk sortering. Kan vara mer minneseffektiv för mycket djupa grafer.
- Minne: BFS kan använda mer minne för breda grafer (med många grannar). DFS kan använda mer stackutrymme för djupa grafer.
Snabbkontroll: val av vägsökningsalgoritm
Du bygger en funktion för ett socialt nätverk som behöver hitta den kortaste förbindelsen (minst antal vänner) mellan två användare. Vilken algoritm passar bäst för den här uppgiften i en oviktad graf?
Sammanfattning och nästa steg
Bra jobbat! I den här lektionen har du lärt dig om de två grundläggande algoritmerna för grafgenomgång:
- Breadth-First Search (BFS): Utforskar lager för lager och passar bra för kortaste vägar.
- Depth-First Search (DFS): Går på djupet och är användbar för att kontrollera konnektivitet eller hitta alla vägar.
Att förstå dessa algoritmer är viktigt för att lösa många grafproblem och hjälper dig att förstå hur grafdatabaser effektivt hittar kopplingar.
Lär dig Grunderna i Neo4j-grafdatabaser 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
- 12
- Lektioner
- 48
Vanliga frågor
Är lektionen ”Algoritmer för vägsökning (BFS, DFS)” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen Grunderna i Neo4j-grafdatabaser, inklusive ”Algoritmer för vägsökning (BFS, DFS)”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i Grunderna i Neo4j-grafdatabaser innehåller totalt 4 lektioner.
Vad lär jag mig i ”Algoritmer för vägsökning (BFS, DFS)”?
Utforska algoritmer som bredden-först-sökning och djupet-först-sökning för att hitta vägar och kopplingar i en graf. Ni övar på Grunderna i Neo4j-grafdatabaser 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 Grunderna i Neo4j-grafdatabaser?
Du behöver inga förkunskaper. Utbildningen i Grunderna i Neo4j-grafdatabaser 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 1 av 4.
Hur lång tid tar lektionen ”Algoritmer för vägsökning (BFS, DFS)”?
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 Grunderna i Neo4j-grafdatabaser-lektionen?
Ja. Varje Grunderna i Neo4j-grafdatabaser-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
- Algoritmer för vägsökning (BFS, DFS)
- Centralitetsalgoritmer (PageRank)
- Algoritmer för gemenskapsdetektering
- Algoritmer för likhet och länkprognoser