BFS

 Coding Problem Keys 

 BFS 

 Problem Statement 

An N*N matrix representation of a graph is given as input, where 1 at Mth row and Nth column denotes node M and node N are connected directly. At 0 denotes the two nodes are disconnected. Perform a breadth first traversal and print the nodes in the traversing order. When visiting the neighboring node, the priority must be given to the node with least value to visit first.

 Example 

1 <= N <= 100

 Input Format 

The first line contains the value of N and source node separated by space(s).
The next N lines contain N elements each separated by space(s).

 Output Format 

The first line contains nodes separated by a space.

 Example Input/Output 1 

 Input 

4 2
1 0 1 1
0 1 0 1
1 0 1 0
1 1 0 1

 Output 

2 4 1 3

 Example Input/Output 2 

 Input 

5 1
1 0 1 0 1
0 1 1 0 0
1 1 1 1 1
0 0 1 1 1
1 0 1 1 1

 Output 

1 3 5 2 4

 Solution 

 Programming Language: C Language 

#include<stdio.h>
#include <stdlib.h>
int queue[1001],l[101][101],k=0,n,rear=0,p=0;
int app(int c){
    int i;
    if(p>k)
    return 0;
    for(i=0;i<n;i++){
        if(l[c][i]==1 && i!=c)
        {queue[k++]=i;
        l[c][i]=-1;
        l[i][c]=-1;
        for(int y=0;y<n;y++)
        l[y][i]=-1;
        }
    }
    return app(queue[p++]);
}
int main(){
    int i,j,c,t=0;
    scanf("%d %d\n",&n,&c);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            scanf("%d ",&l[i][j]);
        scanf("\n");
    }
    c=c-1;
    printf("%d ",c+1);
    app(c);
    for(i=0;i<k;i++)
        printf("%d ",queue[i]+1);
}
// Published By PKJCODERS

 Alter 

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define waiting 2
#define visited 3
int n,start;
int adj[MAX][MAX];
int state[MAX]; 
void create_graph();
void BF_Traversal();
void BFS(int v);
int queue[MAX], front = -1,rear = -1;
void insert_queue(int vertex);
int delete_queue();
int isEmpty_queue();

int main(){
    scanf("%d",&n);
    scanf("%d",&start);
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            scanf("%d",&adj[j][k]);
            BF_Traversal();
            return 0;
}
void BF_Traversal(){
    int v;
    for(v=1; v<=n; v++) 
        state[v] = initial;
        BFS(start);
}
void BFS(int v){
    int i;
    insert_queue(v);
    state[v] = waiting;
    while(!isEmpty_queue()){
        v = delete_queue( );
        printf("%d ",v);
        state[v] = visited;
        for(i=1; i<=n; i++){
            if(adj[v][i] == 1 && state[i] == initial){
                insert_queue(i);
                state[i] = waiting;
            }
        }
    }
    printf("\n");
}
void insert_queue(int vertex){
    if(rear == MAX-1)
        printf("Queue Overflow\n");
    else{
        if(front == -1) 
            front = 0;
            rear = rear+1;
            queue[rear] = vertex;
    }
}
int isEmpty_queue(){
    if(front == -1 || front > rear)
        return 1;
    else
        return 0;
}
int delete_queue(){
    int delete_item;
    if(front == -1 || front > rear){
        printf("Queue Underflow\n");
        return;
    }
    delete_item = queue[front];
    front = front+1;
    return delete_item;
}
// Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.) 

Comments

Popular Posts

ZIGZAG

Number Guessing

Anagram

Function reverseArray

N Numbers Divisible by X or Y

Starting Alphabets a, b and c