Grafo – Busca em Profundidade e Matriz de Adjacência

Continuando a postar exemplos de programa em linguagem C, vou apresentar a resolução de uma trabalho da disciplina de Teoria dos Grafos ministrada em 2009, do aluno Jonathan Schneider, do curso de Bacharelado em Ciência da Computação (UNIVEM).

O conteúdo envolve a criação de um grafo, além de apresentação da criação de matriz de adjacência e também de busca em profundidade.

O código foi testado com Codeblocks usando MingW.

—-

SEGUE O CÓDIGO

————————–

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

typedef struct
{
int topo;
int el[30];
}Pilha;

typedef struct
{
int fim;
int el[30];
}Visitados;

typedef struct
{
int el[30];
}Status ;

typedef struct
{
int adj[30][30];
int indice_inc;
int max;
}Vetor;

void cria_aresta(Vetor *mVetor, int vp, int vu){
// verifica se não se trata de um laço
if (vp==vu){
puts(“\n### ERRO :Primeiro e segundo vertices iguais, nao e permitido lacos ###\n”);

// verifica se a aresta já existe
}else if((mVetor->adj[vp][vu] == 1)||(mVetor->adj[vu][vp] == 1)){
printf(“\n### ERRO : A arresta V%d<—–>V%d ja existe ###\n”,vp,vu);

}else{ // cria aresta na matriz
mVetor->adj[vp][vu] = 1;
mVetor->adj[vu][vp] = 1;
mVetor->indice_inc++;
printf(“\n### CONCLUIDO :Arresta V%d<—–>V%d criada com sucesso ###\n”,vp,vu);

}
}

void apaga_aresta(Vetor *mVetor, int vp, int vu){

// verifica se aresta existe
if (( mVetor->adj[vp][vu]==1) || ( mVetor->adj[vu][vp]==1)) {
//apaga a aresta da matriz de adjacencia
mVetor->adj[vp][vu]=0;
mVetor->adj[vu][vp]=0;
// decrementa o indice
mVetor->indice_inc–;

printf(“\n### CONCLUIDO :Arresta V%d<—–>V%d EXCLUIDA com sucesso ###\n”,vp,vu);
}else{
printf(“\n### ERRO : Impossivel excluir, a aresta %d<—–>V%d nao existe ###\n”,vp,vu);
}
}

void cria_vetores(Vetor *mVetor, Visitados *mvis, Status *mstatus, Pilha *mpilha, int maximo){
//inicializacao da matris de adjacencia grafo
for (int i=0; i for (int j=0; jadj[i][j] = 0;

mVetor->indice_inc=0;
mVetor->max=maximo;

for (int i=0; iel[i]=0;
}
mvis->fim=0;

for (int i=0; iel[i]=0;
}

for (int i=0; iel[i]=0;
}
mpilha->topo=0;

}

void zerabusca(Vetor *mVetor, Visitados *mvis, Status *mstatus, Pilha *mpilha){
int maximo = mVetor->max;
for (int i=0; iel[i]=0;
}
mvis->fim=0;

for (int i=0; iel[i]=0;
}

for (int i=0; iel[i]=0;
}
mpilha->topo=0;
}

void imprime_adj(Vetor *mVetor){
printf(“\n=========================== Matriz de Adjacencia ==============================\n”);
printf(“===============================================================================\n”);

for(int i=0; imax;i++)
if(i==0){
printf(“|\tV0”);
}else if(i!=(mVetor->max-1)){
printf(“\tV%d”,i);
}else{
printf(“\tV%d\t|”,i);
}

for(int i=0; imax;i++){
printf(“\n|V%d\t”,i);
for (int j=0;jmax;j++){
printf(“%d\t”,mVetor->adj[i][j]);
}
printf(“|”);
}
printf(“\n===============================================================================\n\n”);
}

void busca_profundidade(Vetor *mvetor, Visitados *mVis, Status *mstatus, Pilha *mpilha, int inicio){

int novoinicio =99;
// adiciona o vertice inicio a lista de visitados

if(mstatus->el[inicio]!=1){
mVis->el[mVis->fim]= inicio;
mVis->fim++;
mstatus->el[inicio]=1;
// 1 visitado, 2 na pilha, 0 nada feito ainda
}

//i linha, j coluna
for (int i=0; imax; i++)
if(mvetor->adj[i][inicio]==1){
if(novoinicio==99){
if(mstatus->el[i]==0){
novoinicio=i;
}
}else if(mstatus->el[i]!=1){
mpilha->el[mpilha->topo]=i;
mpilha->topo++;
mstatus->el[i]=2;
}
}

if(novoinicio!=99){// se foi encontado um novo vertice não visitado
busca_profundidade(mvetor, mVis, mstatus, mpilha, novoinicio);
}else if(mpilha->topo!=0){// se não foi encontado um novo vertice
mpilha->topo–;

busca_profundidade(mvetor, mVis, mstatus, mpilha, mpilha->el[mpilha->topo]);
//é desempilhado

}else{
printf(“\n==================== Resultado da Busca em Profundidade =======================\n”);
printf(“===============================================================================\n”);

for (int i=0;ifim;i++){
printf(“%d\t”,mVis->el[i]);
}
printf(“\n===============================================================================\n”);
}
}

int main(){
int op,vp,vu,valor,novo;
Vetor mVetor;
Pilha mPilha;
Visitados mVisitados;
Status mStatus;

puts(“\nQuantos Vertices tera o grafo? (Para impressao da matriz na tela: maximo 9)”);
scanf(“%d”,&novo);
cria_vetores(&mVetor,&mVisitados, &mStatus, &mPilha, novo);

puts(“### CONCLUIDO :Novo Grafo iniciado com sucesso ###”);
system (“pause”);

do
{
system(“cls”);

printf(“===============================================================================\n”);
printf(“\n GRAFO.v1.3 – Matriz de Adjacencia/Busca em Profundidade\n”);
printf(“\n===============================================================================\n”);
puts (” 1|- Iniciar Novo Grafo”);
puts (” 2|- Criar Aresta”);
puts (” 3|- Apagar Aresta”);
puts (” 4|- Imprimir Matriz De Adjacencia”);
puts (” 5|- Realizar Busca em Profundidade”);
puts (” 6|- Sair”);
printf(“\n===============================================================================\n”);
scanf(“%d”, &op);
switch(op)
{
case 1: {
puts(“\nTem certeza que deseja inicar um novo Grafo? \n ( 1 = SIM , 0 = NAO )”);
scanf(“%d”,&novo);

if (novo==1){
puts(“\nQuantos Vertices tera o grafo? (Para impressao da matriz na tela: maximo 9)”);
scanf(“%d”,&novo);
cria_vetores(&mVetor,&mVisitados, &mStatus, &mPilha, novo);

puts(“### CONCLUIDO :Novo Grafo iniciado com sucesso ###”);
}else{
puts(“### OPERACAO CANCELADA: Novo Grafo nao iniciado ###”);
}
system (“pause”);
break; }

case 2:{puts(“Digite o PRIMEIRO vertice para a nova aresta:”);
scanf(“%d”,&vp);
puts(“Digite o SEGUNDO vertice para a nova aresta:”);
scanf(“%d”,&vu);
cria_aresta(&mVetor,vp,vu);
system (“pause”);
break; }

case 3:{puts(“Digite o PRIMEIRO vertice da aresta que deseja excluir:”);
scanf(“%d”,&vp);
puts(“Digite o SEGUNDO vertice da aresta que deseja excluir:”);
scanf(“%d”,&vu);
apaga_aresta(&mVetor,vp,vu);
system (“pause”);
break; }

case 4:{ imprime_adj(&mVetor);
system (“pause”);
break; }

case 5:{ zerabusca(&mVetor,&mVisitados, &mStatus, &mPilha);
puts(“Digite o vertice inicial da Busca”);
scanf(“%d”,&vp);
busca_profundidade(&mVetor, &mVisitados, &mStatus, &mPilha, vp);
system (“pause”);
break; }

}
} while (op!=6);
return 1;
}

 

 

Baixe arquivo aqui (após baixar renomeie de .key para .cpp)

Anúncios

Marcado:, , , , , , ,

95 pensamentos sobre “Grafo – Busca em Profundidade e Matriz de Adjacência

  1. KRISTIANO FERNANDES novembro 24, 2010 às 5:19 Reply

    CARA TEM ERROS NA FUNÇÃO DE CRIAR_VETORES
    SE TU PUDESSE ME MANDAR O CODIGO FUNCIONANDO, EU AGRADECERIA.

    • santaremsegundo novembro 24, 2010 às 11:57 Reply

      Prezado Kristiano,
      a função foi testada novamente e está funcionando, procure utilizar outro compilador C.
      Enviei para seu email o arquivo fonte original.

      Até mais…

  2. Rubens novembro 24, 2010 às 16:28 Reply

    Valeu, vc deveria chamar primeiro e não segundo, kkk (brincadeira), me ajudou bastante.

  3. Lucas Emanuel abril 12, 2011 às 23:05 Reply

    Ola poderia me dar o codigo fonte também para me fazer uns testes, copiei o codigo aqui e testei, mas deu alguns erros de compilação.

    abraços…

  4. Nayara Lima maio 18, 2011 às 15:42 Reply

    Tambem nao estou conseguindo compilar o codigo, teria como mandar o fonte para o meu e-mail? preciso com urgeeeeencia
    Desde de ja obg 😀

  5. Thiago maio 22, 2011 às 20:49 Reply

    campeao eu tb tentei copiei e colei porem deu erro, nao tem como vc me mandar o codigo fonte ?!

    abracao velho
    agradecido por tudo !!

  6. Anderson maio 24, 2011 às 16:43 Reply

    Ola cara testei seu codigo e apresenta alguns erros
    voce poderia mandar o codigo fonte para meu email
    sou estudante de Computação e tou precisando da logica desse programa para mim implementar o meu
    fico grato por respostas
    abraço

  7. Guilherme Cássio maio 26, 2011 às 18:41 Reply

    Olá… amigo peguei esse código para tentar dar início no meu, mas… tem alguns erros! Acho que no FOR. Creio eu que estão incompletos?

    void cria_vetores(Vetor *mVetor, Visitados *mvis, Status *mstatus, Pilha *mpilha, int maximo){
    //inicializacao da matris de adjacencia grafo
    for (int i=0; i for (int j=0; jadj[i][j] = 0;

    mVetor->indice_inc=0;
    mVetor->max=maximo;

    for (int i=0; iel[i]=0;
    }
    mvis->fim=0;

    for (int i=0; iel[i]=0;
    }

    for (int i=0; iel[i]=0;
    }
    mpilha->topo=0;

    }

    Se vc poder me ajudar ficaria muito agradecido! Muitão obrigado… ja está de grande ajuda do jeito que está!
    Abraços!
    Qualquer coisa manda por email…

  8. José Everaldo junho 6, 2011 às 10:47 Reply

    Teria como me enviar o código fonte, estou tentando copiar o programa do site e da erro.

    Obrigado

  9. José Heitor Lopes Torres junho 8, 2011 às 18:13 Reply

    Manda pra mim também, cara.
    Tô precisando de um código desses pra um outro problema e queria testar.

    Valeu.

    • J.P novembro 28, 2013 às 8:43 Reply

      Cara, tem como você me enviar o código fonte? Estava precisando para tentar fazer um parecido!Vlw!

      • Eduardo dezembro 5, 2013 às 10:22

        Enviado.

  10. Breno setembro 27, 2011 às 21:52 Reply

    Upa o codigo né? Mo galera pedindo…

    • Misael dezembro 18, 2011 às 12:19 Reply

      Meu deus! tenho um trabalho desses para entregar na faculdade e tô pra morrer aqui kkkkkk
      teria como me enviar o código fonte pra eu poder analisar e tirar minhas duvidas?
      desde já agradeço!

  11. Jeferson Farias Calazans dezembro 4, 2011 às 8:36 Reply

    Olá, eu gostaria que você mandasse o código fonte. Estou tentando compilar o código e não está indo.

  12. johnny fevereiro 21, 2012 às 16:34 Reply

    peguei seu codigo para que eu possa visualizar mais da erro nessa linha
    puts(“\n### ERRO rimeiro e segundo vertices iguais, nao e permitido lacos ###\n”);
    tem um emotion 😛

    oque pode ser. da para me mostrar

    • Eduardo fevereiro 22, 2012 às 18:56 Reply

      Provavelmente na hora de copiar algum caractere estranho foi copiado. Procure redigitar o código.

  13. Marcos março 19, 2012 às 14:04 Reply

    Amigo não consegui compilar, poderia me enviar o codigo original por e-mail. Obrigado,

  14. Edwin maio 22, 2012 às 17:33 Reply

    cara não rodou não tem como enviar o código original to precisando muito já tentei ajeitar mas não consegui

  15. Pedro junho 19, 2012 às 0:16 Reply

    Ai amigo poderia me enviar por e-mail ? Valeu ai adiantado e continue essa ótima explicação de sempre
    OBS: Seu código ta super e bem comentado parabéns pelo site mano abç

  16. Fabrício Melo agosto 26, 2012 às 11:25 Reply

    Cara estou precisando muito deste código, mas copiei e colei e não ta funcionando, teria como me passar por e-mail ?

    Dede já agradeço!

  17. Carol setembro 18, 2012 às 21:27 Reply

    Olá, to precisando do código fonte, me envie por favor 🙂

  18. João setembro 25, 2012 às 0:01 Reply

    Camarada não estar compilando, vc pode enviar o código fonte para meu e-mail? Obrigado pela atenção.

  19. Tais outubro 7, 2012 às 8:51 Reply

    To precisando muito deste código, mas copiei e colei e não ta funcionando, teria como me passar por e-mail ?

    Dede já agradeço!

  20. Rafa outubro 13, 2012 às 16:53 Reply

    Se puder me enviar por email tbm! copiei seu código mais modificou mtos catacteres! Obg 😉

  21. lucasizumi novembro 10, 2012 às 16:24 Reply

    Pode me enviar o código? Tem um for ali que parece estar incompleto, não compila de jeito nenhum. Obrigado.

    • Eduardo novembro 12, 2012 às 9:07 Reply

      Enviado.

      • Thiago Moreira novembro 13, 2012 às 21:51

        Eduardo tem como me enviar o email com o codigo ! Desde já agradeço

      • Thiago M novembro 16, 2012 às 8:48

        Eduardo tem como me enviar tambem está dando uns erros nos for…

        Desde já agradeço.

      • Eduardo novembro 22, 2012 às 14:54

        Enviado.

  22. Leonardo Augusto Testoni Robles março 29, 2013 às 10:52 Reply

    Poderia me enviar o codigo também? Agradeço muito.

  23. Ramyresss abril 5, 2013 às 8:51 Reply

    Em fera envia o codigo pra mim tbm, já que não consegui arrumar o do exemplo para funcionar.

  24. Rogerio maio 11, 2013 às 22:15 Reply

    Me envia o código também please

  25. Rogerio maio 12, 2013 às 16:02 Reply

    Opa Boa Tarde !!

    Envia pra mim por favor!!!!

  26. Tiago maio 27, 2013 às 14:34 Reply

    Poderia me mandar o codigo por favor, pro meu e-mail?

  27. Marcos junho 3, 2013 às 16:47 Reply

    Olá Eduardo!

    Teria como enviar o algoritmo para mim tb. Não consegui compilar copiando do blog.

    Preciso implementar uma busca em profundidade e seu cód. me parece muito interessante.

    Grato.

  28. Salatiel Costa Bairros agosto 9, 2013 às 14:35 Reply

    Olá. teria como enviar o algorítmo para mim também? Desculpe incomodar, mas é que o do post não está compilando.

  29. Mateus agosto 27, 2013 às 14:20 Reply

    Tentei compilar tmb e ta dando erro, poderia me enviar o código fonte ? muito obrigado

  30. Janaina setembro 21, 2013 às 20:08 Reply

    Tem como me enviar o Código fonte também to desesperada com um trabalho da faculdade que não consigo resolver.

  31. Marji setembro 30, 2013 às 9:24 Reply

    Você pode me enviar o fonte? Obrigadinha! 🙂

  32. Hugo Marques outubro 24, 2013 às 23:47 Reply

    Tem como postar o codigo correto ou me mandar, estou precisando muito disto. Agradeço desde já

  33. Rafa novembro 3, 2013 às 16:25 Reply

    Gostei do código esta muito bem escrito e mostra o funcionamento de funções importantes para quem esta estudando.
    Pode enviar no meu email o codigo fonte funcionando por favor?!

    Muito obrigado.

  34. Fernando novembro 21, 2013 às 0:09 Reply

    pode me enviar o código por email ?

  35. Arlei novembro 25, 2013 às 16:13 Reply

    Olá boa tarde poderia me enviar o Código Fonte por e-mail, obrigado.

  36. J.P novembro 28, 2013 às 8:45 Reply

    Tem como você me enviar o código? Estava precisando para fazer um parecido!

  37. Lucas novembro 29, 2013 às 19:28 Reply

    Envie-me o código, por favor.

  38. Lucas novembro 29, 2013 às 19:33 Reply

    Envie-me o código por e-mail, por favor.

  39. Jonathan dezembro 1, 2013 às 21:39 Reply

    Opa, poderia passar o código pro meu email? Necessito muito, ira me ajudar de mais

    obg

  40. Douglas dezembro 2, 2013 às 8:11 Reply

    Podes me enviar o código também ?

  41. Francesco dezembro 2, 2013 às 17:19 Reply

    pode me enviar o código por email? Obrigado desde já

  42. Bruno Matos dezembro 15, 2013 às 10:18 Reply

    Pode me mandar o código fonte?

  43. Junior janeiro 24, 2014 às 18:24 Reply

    Por favor poderia me enviar o código. Desde já agradeço, abrs.

  44. Jucimara fevereiro 28, 2014 às 16:03 Reply

    Ola Eduardo,você poderia me enviar esse código, quero entende -lo, pois meu professor pediu um trabalho parecido, mas tenho que saber que cada linha de código faz, porque vou ter que apresenta-lo.
    email:jucimararodrigues@gmail.com

    Obrigada

  45. Fernando Kiors março 1, 2014 às 23:07 Reply

    Teria como me mandar o codigo fonte.. to precisando de algo assim pra começar uma implementação

  46. Caio março 24, 2014 às 21:41 Reply

    ola . Você pode me enviar o código por favor? desde já agradeço.

  47. Márcio abril 15, 2014 às 2:11 Reply

    Poderia me enviar o código por gentileza? Obrigado

  48. Sr M. maio 19, 2014 às 13:49 Reply

    Pode me enviar o código? Ou melhor, todo os arquivos do programa? Estou estudando sobre o assunto e tenho bastante interesse.

  49. Antonio maio 30, 2014 às 12:08 Reply

    Bom dia amigo, copiei o seu código e não copilou !
    estou precisando p um trabalho na faculdade ! tem como me ajudar ?
    desde já agradeço.

  50. francisco julho 20, 2014 às 22:41 Reply

    Nao to conseguindo copilar vc poderia me mandar por e-mail, desde ja eu agradeço

  51. Lucas setembro 9, 2014 às 9:48 Reply

    Oiii achei interessante seu codigo tb, gostaria que vc me enviasse por e mail o codigo fonte, pois nao conseguir compilar ele daqui ….lucas.zepikeno@gmail.com desde ja agradeço

  52. Edivan Matos outubro 16, 2014 às 11:22 Reply

    Bom dia amigo, voce pode me enviar o codigo, copiei e esta dando erro em:
    puts(“\n### ERRO :Primeiro e segundo vertices iguais, nao e permitido lacos ###\n”);

    • Eduardo novembro 17, 2014 às 21:24 Reply

      No final do código coloquei um link para baixar. Basta renomear depois.

  53. valdiney novembro 13, 2014 às 18:41 Reply

    Porfavor me enviem também, preciso pra um trabalho da facull

    valdineypedro@hotmail.com

    • Eduardo novembro 17, 2014 às 21:24 Reply

      No final do código coloquei um link para baixar. Basta renomear depois.

  54. thiago_cost novembro 17, 2014 às 11:10 Reply

    Olá Eduardo, achei interessante seu codigo , gostaria que vc me enviasse por e mail o codigo fonte, pois nao conseguir compilar.
    email: thiago_cost@hotmail.com
    Desde já agradeço! ABraços

    • Eduardo novembro 17, 2014 às 21:24 Reply

      No final do código coloquei um link para baixar. Basta renomear depois.

  55. Bruno Dal Cas maio 27, 2015 às 11:52 Reply

    Queria teu e-mail pra tirar uma dúvida.., agradeço

  56. Elson Menezes junho 24, 2015 às 12:46 Reply

    Cara vc poderia mandar no meu email também o código por favor?

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s

%d blogueiros gostam disto: