Algorithms Design | Index

Direct manipulation of a queue

Here is a version of the code of the function distances that manipulates the queue directly. In this case, it makes more sense to treat qu, p, and r as local variables:

#define N 100
int dist[N]; // global variable

void distances (int A[][N], int c) {
   int qu[N], p, r;
   for (int j = 0; j < N; ++j)  dist[j] = N;
   dist[c] = 0;
   p = 0; r = 1; qu[0] = c;  // c inserted into queue

   while (p != r) { 
      int i = qu[p++];       // i deleted from queue
      for (int j = 0; j < N; ++j)
         if (A[i][j] == 1 && dist[j] >= N) {
            dist[j] = dist[i] + 1;
            qu[r++] = j;     // j inserted
         }
   }
}

It is perhaps instructive to rewrite the code without the ++:

#define N 100
int dist[N];

void distances (int A[][N], int c) {
   int qu[N], p, r;
   for (int j = 0; j < N; j = j+1)  dist[j] = N;
   dist[c] = 0;
   p = 0; r = 1; qu[0] = c;

   while (p != r) { 
      int i = qu[p]; p = p+1;
      for (j = 0; j < N; j = j+1)
         if (A[i][j] == 1 && dist[j] >= N) {
            dist[j] = dist[i] + 1;
            qu[r] = j; r = r+1;
         }
   }
}