k.c

Implementations of a queue in C with algoritmo BFS, that calculates the minimum distance in a graph.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int Matriz[21][21];
int bfs(int A, int B);
void inicializaMatriz();

typedef struct ListNode_tag {
   int data;
   struct ListNode_tag * next;
} ListNode;

typedef struct {
   ListNode * first;
   ListNode * last;
} queue;

const queue queueEmpty = { NULL, NULL };

void queueInsert (queue * qp, int t){
   ListNode * n = (ListNode *) malloc(sizeof(ListNode));

   if (n == NULL) {
      fprintf(stderr, "Out of memory\n");
      exit(1);
   }

   n->data = t;
   n->next = NULL;

   if (qp->last == NULL)
      qp->first = qp->last = n;

   else {
      qp->last->next = n;
      qp->last = n;
   }
}

int queueRemove (queue * qp){
   ListNode * n;
   int result;
   
   if (qp->first == NULL) {
      fprintf(stderr, "Nothing to remove from an empty queue\n");
      exit(1);
   }

   n = qp->first;
   result = qp->first->data;
   qp->first = qp->first->next;
   free(n);

   if (qp->first == NULL)
      qp->last = NULL;
   return result;
}

int queueHead (queue q){
   if (q.first == NULL) {
      fprintf(stderr, "Nothing to see in an empty queue\n");
      exit(1);
   }
   return q.first->data;
}

int main() {
    int numPaisesLigados, PaisLigado;
	int A, B, i, j, numCasos_N, c, d;
	int conta=0;

	while(scanf("%d",&numPaisesLigados)!=EOF){
       inicializaMatriz();
	   for(i=1; i<20; i++){
          if(i!=1){
            scanf("%d",&numPaisesLigados);
          }	  
	  	  for(j=1; j<=numPaisesLigados; j++){
            scanf("%d",&PaisLigado);
            Matriz[i][PaisLigado] = 1;
	        Matriz[PaisLigado][i] = 1;
          }
       }
       
	   scanf("%d",&numCasos_N);
	   printf("Test Set #%d\n",++conta);
	   for(j=0; j<numCasos_N; j++){
		  scanf("%d %d",&A, &B);
		  int result=bfs(A, B);
	      printf("%2d to %2d: %1d\n",A, B, result);
	   }
	   printf("\n");
	}
	return 0;
}

int bfs(int A, int B){
    int visitado[]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int faz=0, i=0, tamCaminho=0, conta=1, conta_a_seguir=0, flag=0;
	queue q = queueEmpty;   
	queueInsert(&q, A);
	while(faz==0){
	   int inicio_da_fila=queueRemove(&q);
	   conta--;
	   if(conta==0 && flag==1){
		  tamCaminho++;
	   }
	   if(inicio_da_fila==B){
          if(conta==0)
			 return tamCaminho;
          else
			 return tamCaminho+1;
       }
       for(i=1; i<21 ; i++){
		   if(Matriz[inicio_da_fila][i]==1 && visitado[i]!=1){
			  visitado[inicio_da_fila]=1;
			  visitado[i]=1;
			  queueInsert(&q, i);
		      conta_a_seguir++;
			  flag=1;
			}
	   }
	   if(conta==0){
	 	  conta=conta_a_seguir;
		  conta_a_seguir=0;
	   }
	}
}

void inicializaMatriz(){
	int i,j;
	for(i=0; i<21; i++){
		for(j=0; j<21;j++){
			Matriz[i][j] = 0;
        }
    }
}