CODEWITHSUNDEEP
cpathshort
John
John

Reputation: 169

breadth first search - wrong results

This code implements the breadth first search.

#define N 9     //nodes
#define MAXNUM 65555
#define FALSE 0
#define TRUE 1

int main() {
int i, j;
int network[N][N]; //Adjacency matrix
int dist[N]; //distances from node u
int u = 0; //choose first node
void bfs(int, int [N][N], int [N]);

for (i = 0; i < N; i++) {
    dist[i] = MAXNUM;
    for (j = 0; j < N; j++) {
        if (i == j) {
            network[i][j] = 0;
        } else {
            network[i][j] = MAXNUM;
            network[j][i] = MAXNUM;
        }
    }
}

network[0][1]=1; network[0][3]=1; network[0][5]=1;
network[1][0]=1; network[1][2]=1; network[1][6]=1;
network[2][1]=1; network[2][3]=1; network[2][7]=1;
network[3][0]=1; network[3][2]=1; network[3][4]=1;
network[4][3]=1; network[4][5]=1; network[4][7]=1;
network[5][0]=1; network[5][4]=1; network[5][6]=1;
network[6][1]=1; network[6][5]=1; network[6][7]=1;
network[7][2]=1; network[7][4]=1; network[7][6]=1;

bfs(u, network, dist);

return 0;
}

void bfs(int u, int network[N][N], int dist[N]) {
int w, v, onScanQ[N], ScanQ[N], Qsize = 0; 
int k;

for (v = 0; v < N; v++) {
    dist[v] = MAXNUM;
    onScanQ[v] = FALSE;
}

dist[u] = 0;
ScanQ[1] = u;
onScanQ[u] = TRUE;
Qsize = 1;
k = 1;

printf("\nBFS has started examining:\n");

do {
    v = ScanQ[k];
    printf("%d ", v);
    for (w = 0; w < N; w++) {
        if ((network[v][w] < MAXNUM) && (!onScanQ[w])) {
            Qsize++;
            ScanQ[Qsize] = w;
            onScanQ[w] = TRUE;
            dist[w] = dist[v] + 1;
            printf("(%d) ", w);
        }
        k++;
    }
} while (k <= Qsize);
    printf("\n");}

But instead of these results:

BFS has started examining: 0 (1) (3) (5) 1 (2) (6) 3 (4) 5 2 (7) 6 4 7

i take from output, only this:

BFS has started examining: 0 (1) (3) (5)

what's missing?

Upvotes: 1

Views: 209

Answers (1)

Sangeeth Saravanaraj
Sangeeth Saravanaraj

Reputation: 16597

A quick printf inside the while loop shows that your condition in the while is not equated to true and so printed only one set of output!

    printf("Qsize=%d k=%d\n", Qsize, k); 
} while (k <= Qsize);

Output:

Qsize=4 k=10

Upvotes: 1

Related Questions