Ques.Write a program to implement Breadth first traversal of graphs represented using adjacency matrix and list.
Answer :
Breadth-first search : BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. The aim of BFS algorithm is to traverse the graph as close as possible to the root node. Queue is used in the implementation of the breadth first search.
Steps :
- Push the root node in the Queue.
- Loop until the queue is empty.
- Remove the node from the Queue.
- If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue.
Example :
Program :
|
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
def bfs_connected_component(graph, start):
explored = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in explored:
explored.append(node)
neighbours = graph[node]
for neighbour in neighbours:
queue.append(neighbour)
return explored
bfs_connected_component(graph,'A')
|
Output : ['A', 'B', 'C', 'E', 'D', 'F', 'G']
For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments CLICK HERE
| 
| 
