// To implement breadth first search (BFS)

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

int adj[MAX][MAX];
int visit[MAX];
int nodes;

void bfs(int v){
    int i, front, rear;
    int que[MAX];

    front = rear = -1;
    visit[v] = 1;
    printf(" %d ",v);
    rear++;
    front++;
    que[rear] = v;
    while(front<=rear){
        v = que[front];
        front++;
        for(i=1; i<=nodes; i++)
        if( adj[v][i] == 1 && visit[i] == 0){
            visit[i] = 1;
            printf(" %d ",i);
            rear++;
            que[rear] = i;
       }
   }
}

int main(){
    int a[MAX];
    int edges = 0;
    int s, d, i, v;

    printf("\n Enter total no of nodes (max. 20): ");
    scanf("%d", &nodes);
    printf("\n Enter total no of edges (max. %d): ", nodes*(nodes-1));
    scanf("%d", &edges);

    for( i=0; i<edges; i++){
        printf(" Enter edge no %d (src dest): ", i+1);
        scanf("%d %d", &s, &d);
        adj[s][d] = adj[d][s] = 1;
    }

    printf("\n Enter starting node for BFS : ");
    scanf("%d", &v);
    
    printf("\n\t BFS = ");
    for( i=1; i<=nodes; i++)
        visit[i] = 0;
    bfs( v);
    printf("\n ");
    
    system("pause");
    return 0;
}