Breadth First Search Algorithm Explained (With Example and Code)

Breadth First Search Algorithm Explained.
BFS explained with an example and code in Python.
This video is part of my basic algorithms series. Check out the other ones
to develop your algorithm skills and become better at programming or subscribe to this channel for more.

[@sudonick2161]

Damn...you're so underrated...I watched so many videos on the topic and yours was the only one that I found helpful. Thanks a lot, dude..for uploading this.

[@olafschlammbeutel]

Must watch 2020

[@tomarshiv7213]

Pls dfs as well

[@tomarshiv7213]

Dfs???

[@allwinr4802]

This cannot be used to find the shortest path. For the input d = {
1: [2, 3],
2: [1, 3],
3: [1, 2]
}
and the shortest path between 1 and 3,
It returns [1, 2, 3] as the shortest path instead of [1, 3]

[@bonjerne4911]

Hello mate, got same problem with a bit more bigger graph. It will find the shortest path if we will swap 2 and 3 in your example (obviously it will change parent of 3). But I cant figure out what's wrong with algorithm, im pretty sure I miss something simple. Do you have thoughts where to dig?
Thanks anyway.
Edit.
This is works.
def bfs(graph, start, end):
visit = {k: False for k in graph.keys()}
parent = {k: None for k in graph.keys()}
q = Queue()
visit[start] = True
q.put(start)
while not q.empty():
x = q.get()
for v in graph[x]:
if not visit[v]:
visit[v] = True
parent[v] = x
q.put(v)
return short(parent, start, end)
def short(parent, start, end):
path = []
while end is not None:
path.append(end)
end = parent[end]
return path[::-1]

[@Arkonis1]

I think the issue could be fixed if we put after line 12 (in bfsShortestPath) the check that the neighbor node is the endNode, and in that case break the loop.
for example if you add after line 12:
if neighbor == endNode:
return shortestPath(parentNodes, startNode, endNote)
Then it works

[@jonsmith568]

this version of bfs code only works for graphs without cycles, else u need to change the code

[@tanyejie7694]

def dfs(graph,startNode):
visitedNodes = []
queue = [startNode]
while queue:
currentNode = queue.pop()
if currentNode not in visitedNodes:
visitedNodes.append(currentNode)
for neighbour in reversed(graph[currentNode]):
if neighbour not in visitedNodes:
queue.append(neighbour)
return visitedNodes
^Depth-search (use chatgpt for this)