Algorithm - Breadth First Search(BFS) - Python(3)
Problem Definition
Understand and implement BFS in Python
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Python Code
graph = {
'1' : ['2','3'],
'2' : ['4', '5'],
'3' : ['6'],
'4' : ['7'],
'5' : ['6'],
'6' : [],
'7' : ['8'],
'8' : []
}
queued_nodes = []
visited_nodes = []
def bfs(visited_nodes, graph, node):
print ("Following represent graph traverse for node: " + node)
visited_nodes.append(node)
queued_nodes.append(node)
while queued_nodes:
q = queued_nodes.pop(0)
print (q, end = " ")
for neighbour_node in graph[q]:
if neighbour_node not in visited_nodes:
visited_nodes.append(neighbour_node)
queued_nodes.append(neighbour_node)
# Call for Node
bfs(visited_nodes, graph, '2')
Output
Following represent graph traverse for node: 2
2 4 5 7 6 8
Thank you for sharing this Graph algorithm. I really appreciate the author's efforts in presenting so much information in structured way and sharing this valuable post. Learning and practicing data structures and algorithms in Python is essential to build solid programming skills.
ReplyDelete