Pseudo Code
Lektion 4 von 9 im Kurs Breadth-First Search – Graph-Algorithmen von Coddy.
bfs(n, edges, start):
build adjacency (sort each list ascending)
visited = all false
queue = [start]; visited[start] = true
order = []
while queue not empty:
node = queue.dequeue() # vom ANFANG nehmen
order.add(node)
for nb in adj[node]:
if not visited[nb]:
visited[nb] = true
queue.enqueue(nb)
return order- Der einzige Unterschied zu DFS ist der Container: eine Queue (FIFO) anstelle eines Stacks (LIFO).
- Eine einfache Möglichkeit, die Queue zu implementieren, ist ein Array mit einem beweglichen head-Index: Dequeue durch Lesen von
queue[head]und Erhöhen vonhead.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Breadth-First Search – Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)