Skip to content

Instantly share code, notes, and snippets.

@divanibarbosa
Last active Apr 8, 2021
Embed
What would you like to do?
Grafo não orientado e não ponderado sem uso de ponteiros
// 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