Apostila de Grafo

Grafos
(Em Linguagem de Programação C)
Kevim Brasil Maciel
[e-mail]/[e-mail]
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 de adjacê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 uma lista 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 em profundidade e