A search algorithm that checks all neighbours of a node before going ‘deeper’. It uses a queue to store all nodes.
Pseudocode
Algorithm BFS(Graph,start,end):
queue ← Queue ADT
output ← List
visited ← Set ADT
cwn ← Node ADT
Enqueue start to queue
While queue is not Empty do: # O(|V|)
cwn ← Dequeued value from queue
If cwn not in visited then:
Add cwn to visited
Add cwn to output
For edge cwn-v in outgoing edges do: #O(|E|)
If v = end then:
Add end to output
Return output
Else if v is not in visited then: #Only check unseen nodes
Enqueue v to queue
End if
End do
End if
End do
Return "FAIL"
End Algorithm #O(|V| + |E|)
Complexity
Time Complexity:
for queue + for checking outgoing edges =
Given a complete graph, BFS would take i.e. Worst-case it has to check the entire graph via it’s edges and store every node in the queue
Applications
- Exploring social networks
- Searching for a specific webpage in a site
- Shortest Path between 2 nodes
- Cycle detection
Implementation
import networkx as nx
from queue import Queue
def BFS(graph: nx.Graph,start,end):
queue = Queue()
output = list()
visited = set()
queue.put(start)
while not queue.empty():
cwn = queue.get()
if cwn not in visited:
visited.add(cwn)
output.append(cwn)
for (u,v) in graph.edges(cwn):
if v == end:
output.append(end)
return output
elif v not in visited: #Only check unseen nodes
queue.put(v)
return "FAIL"