Breadth First Search or BFS is a type of Graph Traversal.
The idea of BFS is we will start at a vertex then visit ALL vertices of distance 1 from that vertex (all vertices that are connected to that vertex) Then move on to the next vertex and repeat until we have checked ALL vertices.
Not my gif I got this from some YouTube video I can no longer find
Implementation
The implementation of BFS is similar to the iterative implementation of Depth First Search
marked = [False] * G.size()
def bfs(G, v):
queue = [v]
while len(queue) > 0:
v = queue.pop(0)
if not marked[v]:
visit(v)
marked[v] = True
for w in G.neighbors(v):
if not marked[w]:
queue.append(w)