Question
Explain the breadth first search algorithm using the graph given below with v1 as the source vertex:
For each stage of the algorithm give:
i) ),v(d π )v( for each vertex, where )v(d is the distance from the source to the vertex v and is the predecessor of v.
ii) White and gray vertices
iii) Vertices in the queue
Also, give the breadth search tree.
Answer :
Word Count : 764
__________ _____ __________ __________ ___ ________.
________ _________ ___ _____ ________ _____ ___.
____ _______ _______ _____ _________ ____ __________ ________ ___ ____ _______ ________.
__________ __________ ______ ____ ________ ____ ___ __________ ____ ____.
___ _______ ____ _____ ________ _____ _______ __________.
______ ______ _________ _____ _____ ______ ______ ___ _________ ________.
_______ _____ ____ ________ ________ ______ _______ ______ ________.
___ ________ ______ ___ _______ ___ _________ _______ _____ ___ ________.
_________ __________ ___ _________ _____ ________.
_________ _______ ________ ________ ___ _____ __________ ___ _____ ____ _____ ____.
_________ _______ __________ ________ ________ ___ _________.
____ ___ _____ __________ __________ ____ __________.
________ _____ __________ ____ ______ ___ ________ _______ ____.
________ ________ _________ _________ __________ _________ _________ ____.
______ _________ ______ ____ ________ ______ _______ ____.
____ ______ __________ ____ _______.
___ ______ ______ _________ ______.
_____ _____ ____ ______ _____ _____ _______.
______ ______ _____ ___ _____ _________ _________ ____ _____ _____.
___ ____ __________ _____ _____ _____ ___.
____ ____ _______ ________ __________ ______ ______ _____ _________ _____.
______ ______ ____ ___ _______ _________ _____.
__________ _______ ____ __________ ________ ______ _______ _________ __________ _____ _______ _______.
____ ____ _____ _________ _____ ___ ________ _______.
________ ____ _______ ________ ________ ___ ________ ________ __________ ______.
___ _____ ______ ____ _________ ________ ____ ___.
___ ____ ______ _______ _________ ___.
_____ _____ _________ _________ _________ ______ ______ ________ ________.
___ __________ __________ _______ ___.
__________ _____ ______ _________ ________.
_____ ____ ________ ______ ____ _____ ______ ___ _______ ____.
_______ _____ __________ ___ ______ ____ ______ __________.
____ _______ ________ ____ _____ __________ ______.
____ ______ ______ _______ _______ ______ _________ __________ ____ ___ _______ ______.
__________ __________ ___ _________ __________ ____.
_______ ______ ___ ____ ______ ___ ___ __________ __________ _____ ______.
_____ _________ ___ __________ _______ ________ ______.
_______ __________ _________ ____ _____ _____ ____.
_____ _________ ________ __________ ___ ________ ____ __________ _________ _________ _____ ___.
________ ___ _____ ______ _________ ______ ___ _______ _____ ___ _________.
_____ ________ ______ _______ _________ _______ ___.
_______ _________ _______ ____ ________ ___ ______ ___ ___.
________ ____ _____ __________ _____ ______ _______ ______ _________ __________.
_________ _______ _______ ________ ___ _____ __________ ___ ___ _________ ______ ____.
____ ______ ____ ________ ________ _________ __________ _________.
____ __________ ________ _______ ________.
_____ __________ _____ ________ _________ _________ ___ _____ _____ _____ _____.
______ ______ _____ ____ _________ _____ ________ ____ ________ ________.
___ _________ ______ _______ ________ __________ ___ ___ ___ _____ __________ ____.
_______ ___ _____ ___ _____ ______ ______.
_____ ________ _______ ____ _______ __________ ___ ________.
_____ ______ ______ _________ _______.
____ ___ ______ _________ ______ ________ __________ _________ ____.
________ _______ _______ _________ _______ ___.
________ _____ ____ ___ ______ ____.
_________ _____ __________ __________ ____ ________ ___ ______ _______.
___ _____ ____ _____ ________ _________ ______ ______ ________ ______ ____.
_____ ___ ______ _____ _________ ______ ______ _____ ______ ____.
_______ _____ _________ ____ _______ ____ _____ _______ ______ _________ __________.
__________ ___ _________ ______ __________ _____ ________ ____ _______.
____ ___ ___ _____ ___ _____ _________ ___ __________ ____.
_______ ____ _______ _________ _______ ______ ____ ________ ___ ___ _______.
___ _________ _______ _______ _________ _________ ________ ________ _________ __________ __________ _________.
_______ __________ ___ ________ _________ _______ ______ ____ ______ _______ _______.
_____ __________ __________ _________ ____ ________ __________ _________ _____.
_______ ______ _______ __________ ______.
________ _______ ______ __________ ________ __________ ______ ___.
__________ __________ ___ ___ __________.
Skip in 10
To explain the Breadth-First Search (BFS) algorithm in terms of the graph with vertex v1v_1 as the source, here’s how the algorithm proceeds. BFS explores vertices level by level, starting from the source vertex. It uses a queue to track which vertex to visit next.
Initialization:
- Start from the source vertex v1v_1.
- Set d(v1)=0d(v_1) = 0 and π(v1)=null\pi(v_1) = \text{null} because v1v_1 is the starting point.
- All other vertices are initialized with d(v)=∞d(v) = \infty and π(v)=null\pi(v) = \text{null}.
- Mark all vertices as white, which means they are unvisited.
Algorithm Steps:
Step 1: Start with v1v_1
- Queue: [ v1v_1 ]
- d(v1)=0d(v_1) = 0, π(v1)=null\pi(v_1) = \text{null} (since it is the source)
- Gray: [ v1v_1 ] (currently being processed)
- White: All other vertices
- Queue: [ v1v_1 ]
Step 2: Explore neighbors of v1v_1
For each adjacent vertex of v1v_1, update the distance and predecessor:
-
Let's assume v1v_1 is connected to v2v_2 and v3v_3.
- d(v2)=1d(v_2) = 1, π(v2)=v1\pi(v_2) = v_1 (as v2v_2 is reached from v1v_1).
- d(v3)=1d(v_3) = 1, π(v3)=v1\pi(v_3) = v_1 (as v3v_3 is reached from v1v_1).
________ _________ ___ _____ ________ _____ ___.
____ _______ _______ _____ _________ ____ __________ ________ ___ ____ _______ ________.
__________ __________ ______ ____ ________ ____ ___ __________ ____ ____.
___ _______ ____ _____ ________ _____ _______ __________.
______ ______ _________ _____ _____ ______ ______ ___ _________ ________.
_______ _____ ____ ________ ________ ______ _______ ______ ________.
___ ________ ______ ___ _______ ___ _________ _______ _____ ___ ________.
_________ __________ ___ _________ _____ ________.
_________ _______ ________ ________ ___ _____ __________ ___ _____ ____ _____ ____.
_________ _______ __________ ________ ________ ___ _________.
____ ___ _____ __________ __________ ____ __________.
________ _____ __________ ____ ______ ___ ________ _______ ____.
________ ________ _________ _________ __________ _________ _________ ____.
______ _________ ______ ____ ________ ______ _______ ____.
____ ______ __________ ____ _______.
___ ______ ______ _________ ______.
_____ _____ ____ ______ _____ _____ _______.
______ ______ _____ ___ _____ _________ _________ ____ _____ _____.
___ ____ __________ _____ _____ _____ ___.
____ ____ _______ ________ __________ ______ ______ _____ _________ _____.
______ ______ ____ ___ _______ _________ _____.
__________ _______ ____ __________ ________ ______ _______ _________ __________ _____ _______ _______.
____ ____ _____ _________ _____ ___ ________ _______.
________ ____ _______ ________ ________ ___ ________ ________ __________ ______.
___ _____ ______ ____ _________ ________ ____ ___.
___ ____ ______ _______ _________ ___.
_____ _____ _________ _________ _________ ______ ______ ________ ________.
___ __________ __________ _______ ___.
__________ _____ ______ _________ ________.
_____ ____ ________ ______ ____ _____ ______ ___ _______ ____.
_______ _____ __________ ___ ______ ____ ______ __________.
____ _______ ________ ____ _____ __________ ______.
____ ______ ______ _______ _______ ______ _________ __________ ____ ___ _______ ______.
__________ __________ ___ _________ __________ ____.
_______ ______ ___ ____ ______ ___ ___ __________ __________ _____ ______.
_____ _________ ___ __________ _______ ________ ______.
_______ __________ _________ ____ _____ _____ ____.
_____ _________ ________ __________ ___ ________ ____ __________ _________ _________ _____ ___.
________ ___ _____ ______ _________ ______ ___ _______ _____ ___ _________.
_____ ________ ______ _______ _________ _______ ___.
_______ _________ _______ ____ ________ ___ ______ ___ ___.
________ ____ _____ __________ _____ ______ _______ ______ _________ __________.
_________ _______ _______ ________ ___ _____ __________ ___ ___ _________ ______ ____.
____ ______ ____ ________ ________ _________ __________ _________.
____ __________ ________ _______ ________.
_____ __________ _____ ________ _________ _________ ___ _____ _____ _____ _____.
______ ______ _____ ____ _________ _____ ________ ____ ________ ________.
___ _________ ______ _______ ________ __________ ___ ___ ___ _____ __________ ____.
_______ ___ _____ ___ _____ ______ ______.
_____ ________ _______ ____ _______ __________ ___ ________.
_____ ______ ______ _________ _______.
____ ___ ______ _________ ______ ________ __________ _________ ____.
________ _______ _______ _________ _______ ___.
________ _____ ____ ___ ______ ____.
_________ _____ __________ __________ ____ ________ ___ ______ _______.
___ _____ ____ _____ ________ _________ ______ ______ ________ ______ ____.
_____ ___ ______ _____ _________ ______ ______ _____ ______ ____.
_______ _____ _________ ____ _______ ____ _____ _______ ______ _________ __________.
__________ ___ _________ ______ __________ _____ ________ ____ _______.
____ ___ ___ _____ ___ _____ _________ ___ __________ ____.
_______ ____ _______ _________ _______ ______ ____ ________ ___ ___ _______.
___ _________ _______ _______ _________ _________ ________ ________ _________ __________ __________ _________.
_______ __________ ___ ________ _________ _______ ______ ____ ______ _______ _______.
_____ __________ __________ _________ ____ ________ __________ _________ _____.
_______ ______ _______ __________ ______.
________ _______ ______ __________ ________ __________ ______ ___.
__________ __________ ___ ___ __________.
IGNOU ACADEMY
Your IGNOU journey, made easier.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
Continue Reading — It's Free
Sign in with Google to unlock more of this answer.
✓ Free access
✓ Unlock up to 60% of the answer
✓ No payment required
✓ Unlock up to 60% of the answer
✓ No payment required
Quick Google sign-in. No separate registration form.