Traversing using breath first search
Graph algorithm require one systematically examine the nodes and edges of a graph.One way of traversing is called breadth first search.The breadth first search will use a queue as an auxiliary structure to hold nodes for future processing.That is greedy algorithm of graph traversing.
Each node N of G will be in one of three states called status of N.
Status 1:Ready state.
Status 2: Waiting state.
Status 3: Processed state.
Breadth first search
Breadth first search beginning at a starting node A . First examine the starting node A.Then examine all the neighbors of A.This is accomplished by using a queue to hold nodes that are waiting to be processed .
Algorithm
Step 1: Initialize all nodes to the ready state.
Step 2: Put the starting node A in queue and change status to the waiting state.
Step 3: Repeat step 4 and 5 until queue is empty.
Step 4: Remove the front node N of queue .Process N and change the status of N to the processed state.
Step 5: Add to the rear of queue all the neighbors of N that are in the steady state and change their status to the waiting state.
Step 6: Exit.
Example
0 Comments