Breadth-first search (BFS) is an algorithm used for tree traversal on graphs or tree data structures. BFS can be easily implemented using recursion and data structures like dictionaries and lists.
Consider the graph, which is implemented in the code below:
graph = { 'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } visited = [] # List to keep track of visited nodes. queue = [] #Initialize a queue def bfs(visited, graph, node): visited.append(node) queue.append(node) while queue: s = queue.pop(0) print (s, end = " ") for neighbour in graph[s]: if neighbour not in visited: visited.append(neighbour) queue.append(neighbour) # Driver Code bfs(visited, graph, 'A')
Lines 3-10: The illustrated graph is represented using an adjacency list. An easy way to do this in Python is to use a dictionary data structure, where each vertex has a stored list of its adjacent nodes.
Line 12: visited
is a list that is used to keep track of visited nodes.
Line 13: queue
is a list that is used to keep track of nodes currently in the queue.
Line 29: The arguments of the bfs
function are the visited
list, the graph
in the form of a dictionary, and the starting node A
.
Lines 15-26: bfs
follows the algorithm described above:
visited
list and the queue
.Since all of the nodes and vertices are visited, the time complexity for BFS on a graph is $O(V + E)$; where $V$ is the number of vertices and $E$ is the number of edges.
RELATED TAGS
View all Courses