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