Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/10/30
003
004// Busca em largura em grafos: utilizando fila.
005// Exemplo de grafo construido modo "estatico" (vide 'criaGrafo1()' e 'criaGrafo2()'.
006
007// Para evitar construcao ciclica, criar um vetor de nos e cada um com
008// uma lista de vizinhos apontando para o inteiro do vetor.
009
010// $ gcc -fsanitize=address -g -o busca_em_largura busca_em_largura.c
011
012#include <stdio.h>
013#include "../lista_ligada/fila_lista_ligada_struct.h" // estrutura para fila e funcoes para criar, inserir e remover
014
015#define MAXNOS 10 // numero maximo de nos do grafo
016
017typedef struct noV { // Lista de vizinhos
018  int indice;        // supoe que os nos do grafo estao em um vetor
019  struct noV *prox;
020  } Lista;
021
022typedef struct no { // Cada no do grafo
023  int info;
024  Lista *vizinhos;
025  } No;
026
027// Globais
028No    *vetNosGrafo[MAXNOS]; // vetor de nos do grafo
029Lista *vetProxViz[MAXNOS];  // (truque) vetor de nos do grafo com proximo vizinho do no' a ser visitado
030int visitado[MAXNOS];       // auxiliar para marcar os nos visitados
031int inserido[MAXNOS];       // auxiliar para marcar os nos ja inseridos alguma vez na fila
032int nVG;                    // numero de nos do grafo
033tipoRegistroFila *primeiro, *ultimo; // "../lista_ligada/fila_lista_ligada_struct.h" declara 'tipoRegistroFila'
034
035// Lista os vizinhos do no' de indice "i": imprime "indice" e "rotulo" de cada vizinho
036void listaVizinhos (int i) {
037  No *no = vetNosGrafo[i];
038  Lista *viz;
039  int ind;
040  if (no==NULL) { printf("Erro: nao existe o no %d\n", i); return; }
041  if ((viz = no->vizinhos)==NULL) { printf("<vazio>\n"); return; }
042  while (viz != NULL) {
043    ind = viz->indice;
044    printf("<%d: ", ind);
045    printf("%d > ", vetNosGrafo[ind]->info);
046    viz = viz->prox;
047    }
048  printf("\n");
049  }
050
051
052// Atencao, precisa de alocacao dinamica e antes de voltar para quem chamou,
053// e' necessario que alguma variavel de quem chamou preserve os apontadores.
054void criaGrafo1 () { // Grafo 1                       (1)---(2)
055  nVG = 4;                   // num. nos do grafo      |  \  |
056  No *no1, *no2, *no3, *no4; //                       (3)---(4)
057  Lista *lista1, *lista2, *lista3,
058        *lista4, *listaAux; // uma lista de adjacentes para cada no
059  no1 = malloc(sizeof(No)); no2 = malloc(sizeof(No));
060  no3 = malloc(sizeof(No)); no4 = malloc(sizeof(No));
061  no1->info = 1; no2->info = 2; no3->info = 3; no4->info = 4;
062  vetNosGrafo[0] = no1;          // No 1 : tem como vizinhos 2, 3, 4 - neste ponto preserva-se os end alocados
063  listaAux = malloc(sizeof(Lista)); listaAux->indice = 1; // no 2
064  lista1   = listaAux;
065  listaAux = malloc(sizeof(Lista)); listaAux->indice = 2; // no 3
066  lista1->prox = listaAux;
067  listaAux = malloc(sizeof(Lista)); listaAux->indice = 3; // no 4
068  listaAux->prox = NULL;
069  lista1->prox->prox = listaAux; vetProxViz[0] = lista1;
070  no1->vizinhos = lista1;
071  vetNosGrafo[1] = no2;          // No 2 : tem como vizinhos 1, 4
072  listaAux = malloc(sizeof(Lista)); listaAux->indice = 0; // no 1
073  lista2   = listaAux;
074  listaAux = malloc(sizeof(Lista)); listaAux->indice = 3; // no 4
075  listaAux->prox = NULL;   
076  lista2->prox = listaAux; vetProxViz[1] = lista2;
077  no2->vizinhos = lista2;   
078  vetNosGrafo[2] = no3;          // No 3 : tem como vizinhos 1, 4
079  listaAux = malloc(sizeof(Lista)); listaAux->indice = 0; // no 1
080  lista3   = listaAux;
081  listaAux = malloc(sizeof(Lista)); listaAux->indice = 3; // no 4
082  listaAux->prox = NULL;   
083  lista3->prox = listaAux; vetProxViz[2] = lista3;
084  no3->vizinhos = lista3;   
085  vetNosGrafo[3] = no4;          // No 4 : tem como vizinhos 1, 2, 3
086  listaAux = malloc(sizeof(Lista)); listaAux->indice = 0; // no 1
087  lista4   = listaAux;
088  listaAux = malloc(sizeof(Lista)); listaAux->indice = 1; // no 2
089  lista4->prox = listaAux;
090  listaAux = malloc(sizeof(Lista)); listaAux->indice = 2; // no 3
091  listaAux->prox = NULL;   
092  lista4->prox->prox = listaAux; vetProxViz[3] = lista4;
093  no4->vizinhos = lista4;
094  }
095
096void criaGrafo2 () { // Grafo 2                       (1)---(2)
097  nVG = 4;                   // num. nos do grafo            |  \     (nao terminar em '\')
098  No *no1, *no2, *no3, *no4; //                             (3)---(4)
099  Lista *lista1, *lista2, *lista3,
100        *lista4, *listaAux; // uma lista de adjacentes para cada no
101  no1 = malloc(sizeof(No)); no2 = malloc(sizeof(No));
102  no3 = malloc(sizeof(No)); no4 = malloc(sizeof(No));
103  no1->info = 1; no2->info = 2; no3->info = 3; no4->info = 4;
104  vetNosGrafo[0] = no1;          // No 1 : tem como vizinhos 2
105  listaAux = malloc(sizeof(Lista)); listaAux->indice = 1; // no 2
106  listaAux->prox = NULL;   
107  lista1   = listaAux; vetProxViz[0] = lista1;
108  no1->vizinhos = lista1;
109  vetNosGrafo[1] = no2;          // No 2 : tem como vizinhos 1, 3, 4
110  listaAux = malloc(sizeof(Lista)); listaAux->indice = 0; // no 1
111  lista2   = listaAux;
112  listaAux = malloc(sizeof(Lista)); listaAux->indice = 2; // no 3
113  lista2->prox = listaAux;
114  listaAux = malloc(sizeof(Lista)); listaAux->indice = 3; // no 4
115  listaAux->prox = NULL;
116  lista2->prox->prox = listaAux; vetProxViz[1] = lista2;
117  no2->vizinhos = lista2;   
118  vetNosGrafo[2] = no3;          // No 3 : tem como vizinhos 2, 4
119  listaAux = malloc(sizeof(Lista)); listaAux->indice = 1; // no 2
120  lista3   = listaAux;
121  listaAux = malloc(sizeof(Lista)); listaAux->indice = 3; // no 4
122  listaAux->prox = NULL;   
123  lista3->prox = listaAux; vetProxViz[2] = lista3;
124  no3->vizinhos = lista3;   
125  vetNosGrafo[3] = no4;          // No 4 : tem como vizinhos 2, 3
126  listaAux = malloc(sizeof(Lista)); listaAux->indice = 1; // no 2
127  lista4   = listaAux;
128  listaAux = malloc(sizeof(Lista)); listaAux->indice = 2; // no 3
129  listaAux->prox = NULL;   
130  lista4->prox = listaAux; vetProxViz[3] = lista4;
131  no4->vizinhos = lista4;
132  }
133
134void iniciaVisitados (int n) { // inicia cada no' como NAO visitado e NAO inserido na fila
135  int i;
136  for (i=0; i<n; i++) {
137    visitado[i] = 0; // marque como NAO visitado
138    inserido[i] = 0; // marque como NAO inserido
139    }
140  }
141
142void visite (int i) { // Visite o no'
143  printf("<%d: ", i);
144  if (vetNosGrafo[i]==NULL) { printf("x > - erro! 'visite(%d)'!\n", i); return ; } //S seguranca
145  printf("%d > ", vetNosGrafo[i]->info);
146  visitado[i] = 1; // marque como visitado
147  }
148
149int temVizinho (No *item) { // Verifica se o no' tem algum vizinho
150  if (item==NULL) { printf("Erro! 'temVizinho(NULL)'!\n"); return 0; } //S seguranca
151  return item->vizinhos!=NULL; // se nao NULL => tem filhos
152  }
153
154// Truque para pegar iterativa (a cada chamada) os vizinhos de um no'
155int proximoVizinho (int indice) { // devolva proximo vizinho de vetNosGrafo[indice]
156  Lista *viz = vetProxViz[indice]; // pegue atual vizinho do no de indice dado
157  if (viz==NULL) { //D printf("<sem vizinhos>");
158    return -1; // este no NAO tem vizinhos!
159    }
160  vetProxViz[indice] = viz->prox;  // avance para o seguinte
161  return viz->indice; // devolva indice do ultimo
162  }
163
164// Algoritmo de busca em largura.
165// Utiliza uma fila para inserir vizinhos de cada no' visitado.
166// Usa vetor de "bits" (visitado[], inserido[]) para marcar visitados e inseridos.
167void buscaEmLargura (int vg) { // recebe primeiro elemento da fila
168  No *aux, *no = vetNosGrafo[0];
169  tipoRegistroFila *item;
170  int ind, aux_ind, conta = 0;
171  item = criarRegFila(0, "no"); // define item->ind = conta
172  iniciaVisitados(vg);
173  inserirFila(&primeiro, &ultimo, item); inserido[0] = 1; // marque como inserido
174  while (filaNaoVazia(primeiro)) { // ../lista_ligada/fila_lista_ligada_struct.h: filaNaoVazia(...)
175    //D printf("Indices na fila: "); imprimirFilaToda(primeiro); 
176    item = removerFila(&primeiro, &ultimo);
177    ind = item->ind;
178    //D printf("\n-------------\nbuscaEmLargura: conta=%d, item->ind=%d\n", conta, ind);
179    if (visitado[ind]==0) { // verifica se item ainda nao foi visitado
180      visite(ind); printf(" : ");
181      //D printf(" vizinhos de item->ind=%d (vetProxViz[%d]->indice=%d): ", ind, ind, vetProxViz[ind]->indice);
182      while ((aux_ind = proximoVizinho(ind))>=0) {
183        if (inserido[aux_ind]!=1) { // insere apenas se NAO foi inserido antes
184          item = criarRegFila(aux_ind, "no"); conta++;
185          inserirFila(&primeiro, &ultimo, item); inserido[aux_ind] = 1; // marque como inserido
186          //D printf("(v=0, item->ind=%d) ", item->ind);
187          printf(" <%d, %d> ", item->ind, vetNosGrafo[aux_ind]->info);
188          }
189        else printf("[%d, %d] ", aux_ind, vetNosGrafo[aux_ind]->info); // ja inserido
190        }
191      }
192    //D else printf(" %d ja foi visitado *****\n", ind);
193    printf("\n");
194    } // while (filaNaoVazia(primeiro))
195  } // void buscaEmLargura (int vg)
196
197
198int main (void) {
199  int i;
200  printf("Simulando operacoes: nos\n");
201  criaGrafo2(); // nVG = 4
202  for (i=0; i<nVG; i++) { // inserir os 5 item
203    printf("%d: ", vetNosGrafo[i]->info);
204    listaVizinhos(i);
205    }
206  buscaEmLargura(nVG);
207  printf("\n");
208
209  return 0;
210  }