GO Classes DPP | PYTHON & DSA |BFS

Answer 1

Step 1: Initialize the BFS

 

The Breadth First Search (BFS) starts at vertex 1. A queue is used to keep track of vertices to visit, and a set tracks visited vertices. The neighbors of each vertex are listed in increasing order, which determines the order they are added to the queue.

• Queue:
• Visited: {1}
• Traversal Order:

Step 2: Process vertex 1

 

Dequeue 1. Its neighbors (from the image) are 2 and 3 (in increasing order). Add them to the queue and visited set.

• Queue:
• Visited: {1, 2, 3}
• Traversal Order:

Step 3: Process vertex 2

 

Dequeue 2. Its neighbors are 1, 4, 5. Vertex 1 has already been visited. Add 4 and 5 to the queue and visited set.

• Queue:
• Visited: {1, 2, 3, 4, 5}
• Traversal Order:

Step 4: Process vertex 3

 

Dequeue 3. Its neighbors are 2 and 6. Vertex 2 has already been visited. Add 6 to the queue and visited set.

• Queue:
• Visited: {1, 2, 3, 4, 5, 6}
• Traversal Order:

Step 5: Process vertex 4

 

Dequeue 4. Its only neighbor is 2, which has been visited.

• Queue:
• Visited: {1, 2, 3, 4, 5, 6}
• Traversal Order:

Step 6: Process vertex 5

 

Dequeue 5. Its neighbors are 2 and 7. Vertex 2 has been visited. Add 7 to the queue and visited set.

• Queue:
• Visited: {1, 2, 3, 4, 5, 6, 7}
• Traversal Order:

Step 7: Process vertex 6

 

Dequeue 6. Its only neighbor is 3, which has been visited.

• Queue:
• Visited: {1, 2, 3, 4, 5, 6, 7}
• Traversal Order:

Step 8: Process vertex 7

 

Dequeue 7. Its only neighbor is 5, which has been visited. The queue is now empty.

• Queue: []
• Visited: {1, 2, 3, 4, 5, 6, 7}
• Traversal Order:

Answer: (a) 1234567