Last active
April 8, 2021 01:12
-
-
Save divanibarbosa/0a7b4fdfc6ebd3020c1bd5c1401bed9d to your computer and use it in GitHub Desktop.
Grafo não orientado e não ponderado sem uso de ponteiros
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Criado por: profa. Divani Barbosa Gavinier | |
// Curriculo Lattes: http://lattes.cnpq.br/8503400830635447 | |
// divanibarbosa@gmail.com | |
#include <stdio.h> | |
#include <stdlib.h> | |
#define MAX 10 // quantidade maxima de Nos | |
/////////////////////////////////////// | |
// VARIAVEIS GLOBAL PILHA | |
int itens[MAX], topo, tam; | |
/////////////////////////////////////// | |
// FUNÇÕES PILHA | |
void Inicia_Pilha(int n) { | |
tam = n; | |
topo = 0; | |
} | |
void push(int valor) { // empilha | |
itens [ topo ] = valor; | |
topo++; | |
} | |
void pop() { topo--; } // desempilha | |
int top() { return itens[ topo-1 ]; } // consulta topo | |
int empty() { return ( topo == 0 ); } // pilha vazia? | |
/////////////////////////////////////////////// | |
// ESTRUTURA NO PARA SER USADA NO GRAFO | |
typedef struct { | |
char item; | |
int visitado; | |
} NO; | |
/////////////////////////////////////// | |
// VARIAVEIS GLOBAL GRAFO | |
NO VetorNos[MAX]; // vetor de nós | |
int MatAdj[MAX][MAX]; // matriz de adjacência | |
int nNOs; // numero de nós | |
/////////////////////////////////////////////// | |
// FUNÇÕES GRAFO | |
void Inicia_Grafo(int n) { | |
// n = quantidade maxima de Nos | |
int i, j; | |
for (j=0; j<n; j++) // inicializando matriz de adjacencia | |
for (i=0; i<n; i++) | |
MatAdj[i][j] = 0; | |
nNOs = 0; | |
Inicia_Pilha(n); | |
} | |
void insereNO(char v) { | |
VetorNos[nNOs].item = v; | |
VetorNos[nNOs].visitado = 0; | |
nNOs++; | |
} | |
void insereAresta(int inicio, int fim) { | |
MatAdj[inicio][fim] = 1; | |
MatAdj[fim][inicio] = 1; | |
} | |
void mostraNo(int v) { | |
printf("%c ",VetorNos[v].item); | |
} | |
// Retorna Nó que não foram visitados e são adjacentes ao Nó passado como parametro | |
int NoNaoVisitado(int i) { | |
int j; | |
for (j=0; j<nNOs; j++) | |
if (MatAdj[i][j]==1 && VetorNos[j].visitado==0) | |
return j; | |
return -1; | |
} | |
// Algoritmo Busca por profundidade (dfs) | |
// Esse algoritmo possui um laço até que a pilha esteja vazia, onde são realizadas 4 tarefas: | |
// 1- Examinar o Nó do topo da pilha, usando metodo top | |
// 2- Tentar encontrar um vizinho não visitado desse Nó | |
// 3- Se não encontrar um, desempilha | |
// 4- Se encontrar o Nó, visita ele (marca como visitado) e empilha-o | |
void dfs() { | |
VetorNos[0].visitado = 1; // Começa visitando o Nó zero | |
mostraNo(0); // Exibe o Nó zero | |
push(0); // Empilha o Nó zero | |
while(!empty()) { // enquanto a pilha NAO esta vazia | |
int v = NoNaoVisitado(top()); | |
if ( v == -1) // Se nao houver Nó NAO visitado | |
pop(); // desempilha | |
else { | |
VetorNos[v].visitado = 1; // Visita o Nó | |
mostraNo(v); // Exibe o Nó | |
push(v); // Empilha o Nó | |
} | |
} // fim while | |
// Aqui a pilha esta vazia, chegou no final | |
int i; | |
for (i=0; i<nNOs; i++) // redefine flags para uso posterior se necessário | |
VetorNos[i].visitado = 0; | |
} | |
/////////////////////////////////////////////// | |
// PROGRAMA PRINCIPAL | |
main() { | |
Inicia_Grafo(MAX); | |
insereNO('A'); // 0 | |
insereNO('B'); // 1 | |
insereNO('C'); // 2 | |
insereNO('D'); // 3 | |
insereNO('E'); // 4 | |
insereNO('F'); // 5 | |
insereNO('G'); // 6 | |
insereNO('H'); // 7 | |
insereNO('I'); // 8 | |
insereAresta(0, 1); // AB | |
insereAresta(1, 5); // BF | |
insereAresta(5, 7); // FH | |
insereAresta(0, 2); // AC | |
insereAresta(0, 3); // AD | |
insereAresta(3, 6); // DG | |
insereAresta(6, 8); // GI | |
insereAresta(0, 4); // AE | |
printf("Visitada DFS: "); | |
dfs(); // Busca em profundidade ou largura | |
printf("\n"); | |
system("pause"); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment