Breadth First Search

Lets see BFS(Breadth First Search) traversal of an undirected graph using a non recursive function.

What is BFS ?

It is a graph traversal in which you start from the source vertex.(2 here)

You visit all the adjacent vertices before moving on to the next level neighbours.

Blue    ---> current vertex

Yellow ---> visited vertices

Algorithm

Let source vertex be current vertex.

a.Mark current vertex as visited and enqueue it.

b.Till queue is not empty
       Dequeue a vertex and make it current.Print it.Visit adjacent unvisited vertices 
       of current vertex.Mark them visited,enqueue them.

Code

See how to implement queue using array

void read_graph()
{
    int i,j;

    printf("Enter the no of vertices in the graph ");
    scanf("%d",&n);

    printf("\nEnter adjacency matrix\n");

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            scanf("%d",&adj_mat[i][j]);

        vis[i] = 0;
    }
}

void bfs()
{
    int curr = 1,i = 2;
    vis[curr] = 1;

    init();

    enqueue(curr);

    while(!isEmpty())
    {
        curr = dequeue();
        printf("%d ",curr);
        i = 1;

        while(i<=n)
        {
            if(vis[i]==0 && adj_mat[curr][i]==1)
            {
                vis[i] = 1;
                enqueue(i);

            }

            i++;
        }
    }
}

Code Tracing

Complete code