# implementation of Breadth first traversal of graphs represented using adjacency matrix and list.

0 like 0 dislike
562 views

edited
Write a program to implement Breadth first traversal of graphs represented using adjacency matrix and list.

## 1 Answer

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

Best answer

## 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  :

1. Push the root node in the Queue.
2. Loop until the queue is empty.
3. Remove the node from the Queue.
4. 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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.