I have to write a program that does BFS traversal. My code is mostly correct but i have an error somewhere. it prints repeated numbers in some cases and it's not supposed to. i'm not sure exactly what the problem is. I really hope someone will be able to help me fix it soon. I think the error is after the comment that says "filling BFS array". I dont know what i did wrong. PLEASE HELP!!
This is the orignal question:
Given an undirected graph and a source, please output the traversal order of BFS from
the given source. If there are many answers, please output the smallest alphabetical
order.
P.S. alphabetical order: for example 1 2 3 4 5 < 1 3 2 4 5 < 1 3 4 2 5
Input
There are many cases in input.
The first line in the input contains three integers: n, m, and src, representing the
number of nodes in the graph, the number of edges in the graph and the source.
The next m lines, each line contains 2 integers, u and v (1<=u, v <= n). That means
there is an edge between u and v. There is at most one edge between two nodes.
n <= 1000
m <= n*(n-1)/2
1 <= src <= n
*Output
For each case output the traversal order of BFS from the source.
Sample Input
552
21
13
42
35
51
Sample Output
Case 1: 2 1 4 3 5
Here is my code:*
#include<stdio.h>
#include<stdlib.h>
int main()
{
int nodes, edges, src, i, num1, num2;
scanf("%d", &nodes);
scanf("%d", &edges);
scanf("%d", &src);
int matrix[nodes][nodes];
int r, c, cc;
for(r = 0; r < nodes; r++){ //initializing matrix
for (c = 0; c < nodes; c++){
matrix[r][c]= -1;
}
}
for(i = 0; i < edges; i++) // filling adjacency matrix
{
scanf("%d%d", &num1,&num2);
matrix[num1 - 1][num2 - 1] = 1;
matrix[num2 - 1][num1 - 1] = 1;
}
int adjList[nodes][nodes];
for(r = 0; r < nodes; r++){ //initializing adjancency list
for (c = 0; c < nodes; c++){
adjList[r][c]= -1;
}
}
for(r = 0; r < nodes; r++){ //filling adjacency list
for (c = 0, cc = 0; c < nodes; c++){
if(matrix[r][c] == 1)
{
adjList[r][cc] = c+1;
cc++;
}
}
}
int order[nodes]; //array to store BFS order of the nodes
int row, col, check, current = 0, value;
order[current] = src;
for(row = src - 1; current < nodes; ) //filling BFS array
{
for(col = 0; (col < edges && adjList[row][col] != -1); col++ )
{
value = adjList[row][col];
for(check = 0; check < nodes && order[check] != value; check ++) //checking to make sure that the adjacency list value hasn't already been put into the order list
{
;
}
if(check = nodes)
{
current++;
order[current] = adjList[row][col];
}
else continue;
}
row = order[current] - 1;
}
int x;
for(x = 0; x < nodes; x++)
{
printf("%d ", order[x]);
}
return 0;
}