Apostila de Grafo

Páginas: 10 (2370 palavras) Publicado: 15 de maio de 2014
Grafos
(Em Linguagem de Programação C)
Kevim Brasil Maciel
Kevim_brasil@hotmail.com/kevim.maciel@gamail.com
Graduando Em Ciência Da Computação
Manaus/AM 2013


Grafos é um conjunto não-vazio de vértices e arestas, tais que cada arco conecta dois nós, ou seja G(V,A). De forma mais simples, um grafo é um conjunto de pontos e arcos, e esses arcos conectam esses pontos (ou nós).Nesta apostila estudaremos a implementação do algoritmo para grafos não direcionados, não trabalharemos com grafos ponderados, pois ao final das explicações o leitor terá a capacidade de implementa-la facilmente.
Então dividimos assim o estudo dos grafos:
Grafo não direcionado:
Registro;
Main;
Menu;
Inserção das Arestas;
Impressão da lista deadjacência;
Busca em largura;
Busca em profundidade;
Para o garfo direcionado, a única coisa que mudará será a inserção das arestas, você utilizara somente o primeiro teste que é demonstrado na função.
Registro
O registro é onde ficara as informações sobre o que cada espaço de memória terá que armazenar. Em relação ao registro você pode utilizar duas formas simples,uma consiste em apenas um espaço de memória de um ponteiro para uma lista de encadeada, o outro armazenará não só um ponteiro mais também qual ponto é aquele. Daremos ênfase somente a que possui dois campos, pois sua lista de adjacência será do mesmo tipo que ela, logo não precisaremos criar outro registro.
Registro com dois campos. Um para guardar o ponto do grafo e outro um ponteiro para umalista de adjacência, lista de adjacência são todos os pontos para qual aquele ponto está ligado:
typedef struct x{
int num;
struct x *prox;
}x;
Aqui chamamos o tipo abstrato de dado de “x”, mas você pode colocar o nome que desejar. O registro consiste somente nisso. Mas como trabalhamos com busca em largura e em profundidade teremos mais alguns registros, um será utilizado na busca emprofundidade e ambos serão utilizados na busca em largura.
typedef struct pilha{
int num;
struct pilha *prox;
}pilha;
Esse registro será utilizado em ambas as buscas, vale lembrar que a busca em profundidade trabalha com a ideia da pilha (LIFO) o primeiro que entra é o último a sair, e a busca em largura trabalha coma ideia da fila (FIFO) o primeiro que entra é o primeiro que sai.
typedefstruct sentinela{
struct pilha *inicio;
struct pilha *fim;
}sentinela;
A sentinela, caso você não lembre, guarda o início e o final da fila, e é com o auxílio dela que trabalharemos a busca em largura.

Main
Na main criaremos o ponteiro para o grafo, pois até agora não sabemos o tamanho dele, digo-lhes que é muito mais prático fazer um grafodinamicamente, caso contrário toda vez que seu professor mudar o tamanho do grafo você terá que alterar seu código.
Nela havemos de ler do usuário o tamanho do grafo, ou seja, quantos pontos ele possui, e chamamos a função menu, que ficara encarregada da continuação do algoritmo.
Vejamos a Main:
int main(){
x *grafo=NULL;
int tam;
printf("Tamanho do vetor: ");
scanf("%d",&tam);grafo=(x *)malloc(tam * sizeof(x));

if(!grafo){
puts("ERRO\n");system("pause");exit(0);
}
system("cls");

menu(grafo,tam);
}

Menu
A função menu, consiste apenas em inicializar todos os campos do nosso grafo e ler do usuário qual a opção desejada e a parti daí chamar as funções correspondente a escolha.
void menu(x *grafo, int tam){int op,i;


for(i=0;inum=n2;
novo->prox=NULL;
novo->prox=grafo[n1].prox;
grafo[n1].prox=novo;
}
Caso contrário, ele aloca dois espaços em memória, um para cada número, lembrando novamente de que como não é um grafo direcionado, ambos apontam para ambos.
else{
novo=(x *)malloc(sizeof(x));
novo->prox=NULL;
novo->num=n2;
novo->prox=grafo[n1].prox;...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Apostila De Teoria Dos Grafos
  • Grafos
  • Grafos
  • Grafos
  • Grafo
  • grafos
  • Grafos
  • Grafos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!