Exercício Aula 4 - Teoria dos Grafos

Prévia do material em texto

Exercício Aula 4 - Digrafo 
 
Crie um algoritmo que procure um caminho utilizando matriz de adjacência entre um vértice de 
origem e um vértice de destino O usuário entra com os vértices de origem e destino 
 
 
 
 
Código de Resolução: 
 
#include <stdio.h> 
#include <stdlib.h> 
 
#define qtdVertices 8 
 
int tamanhoVetor(int vetor[]); 
void imprimeVetor(int a[]); 
 
int main() { 
 int matriz[qtdVertices][qtdVertices] = { {0,1,0,0,0,0,0,0}, {0,0,1,1,0,0,0,0}, {1,1,0,0,0,0,0,0}, 
{0,0,1,0,1,0,1,0}, {0,0,0,0,0,0,1,0}, {0,0,0,1,0,0,0,0}, 
{0,0,0,1,0,1,0,1}, {0,0,0,0,0,0,1,0} }; 
 int caminho[qtdVertices] = {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL}; 
 int i, j, p, flag =0,origem = 0, destino = 0; 
 
 printf("---- Digrafo - Encontrando caminho pela matriz de adjacencia ----\n\n"); 
 printf("Insira o vertice de origem: "); 
 scanf("%d", &origem); 
 printf("Insira o vertice de destino: "); 
 scanf("%d", &destino); 
 
 if(origem == destino){ 
 printf("\n\nVoce ja se encontra no seu destino!"); 
 exit(0); 
 } 
 
 caminho[0] = origem; 
 for(i=origem-1; i < qtdVertices; i++){ 
 for(j=0; j < qtdVertices; j++){ 
 if(matriz[i][j] == 1){ 
 if(j+1 == destino){ 
 caminho[tamanhoVetor(caminho)] = destino; 
 imprimeVetor(caminho); 
 exit(0); 
 }else{ 
 for(p = 0; p < tamanhoVetor(caminho); p++){ 
 if(caminho[p] == j+1){ 
 flag = 1; 
 }} 
 if(flag == 1){ 
 matriz[i][j]= 0; 
 flag=0; 
 }else{ 
 caminho[tamanhoVetor(caminho)] = j+1; 
 matriz[i][j]= 0; 
 i=j; 
 j = -1; 
 }}}} 
 if(tamanhoVetor(caminho) > 1){ 
 caminho[tamanhoVetor(caminho)-1]= NULL; 
 i = caminho[tamanhoVetor(caminho)-1]-2; 
 }else{ 
 printf("\n\nCaminho Inexistente!"); 
 exit(0); 
 }} 
 return 0; 
} 
 
 
void imprimeVetor(int a[]){ 
 int x; 
 printf("\n\nCaminho Encontrado: %d", a[0]); 
 for(x=1; x < tamanhoVetor(a); x++){ 
 printf(" ==> %d", a[x]); 
 } 
} 
int tamanhoVetor(int vetor[]){ 
 int cont = 0, a; 
 for(a = 0; a < qtdVertices; a++){ 
 if(vetor[a]!= NULL){ 
 cont++; 
 } 
 } 
 return cont; 
}