Estrutura de Dados

ESTRUTURAS DE DADOS 2
GRAFOS - ALGORITMOS
Listas de Adjacência
Definição do tipo das listas de adjacência, sendo que são implementadas com listas ligadas. Tipo de um nodo da lista. typedef struct nodo
{ VERTICE v; struct nodo * next;
} NODO;
Apontador para este nodo. typedef NODO * ADJ;

O grafo pode agora ser definido como um sequência (array) de apontadores para as listas de adjacência (N é o numero de vértices do grafo).
ADJ GRAFO[N];

Esta definição, porém, implica que estaticamente se especifique qual o número máximo de vértices que um dado grafo pode conter, definindo como uma sequência de apontadores para as listas de adjacência: typedef ADJ * GRAFO;
OBS: E dinamicamente construir uma sequência de apontadores igual ao número máximo de vértices de um dado grafo.
Tipo dos vértices dos grafos. typedef int VERTICE;
Definições para simplificar o acesso aos vários campos de um nodo da lista ligada de adjacências, para testar se a lista é vazia e para criar um novo nodo da lista.
#define EL(n) n->v
#define NEXT(l) l->next
#define EMPTY(l) (l == NULL)
#define CONSNODO (ADJ)malloc(sizeof(NODO))
Inclusão do tipo das funções que manipulam o grafo e as listas ligadas de adjacência:
GRAFO novo_grafo (int nvertices);
GRAFO add_ramo (GRAFO g , VERTICE v1,VERTICE v2);
ADJ sucessores (GRAFO g , VERTICE v);
BOOLEAN is_sucessor (GRAFO g , VERTICE v1 , VERTICE v2); void show_sucessores (GRAFO g , VERTICE v);
ADJ antecessores (GRAFO g , VERTICE v);
ADJ ins_lista_adjacentes (ADJ l , VERTICE v); void show_lista_adjacentes (ADJ l);

A implementação dos grafos:
#include "listas_adj.h"
Criar um novo grafo corresponde.
GRAFO novo_grafo(int nvertices)
{ GRAFO g; int i; g = (GRAFO)malloc( sizeof(ADJ) * nvertices ); for (i = 0 ; i < nvertices ; ++i)
*(g+i) = NULL; return g;
}
Adicionar uma aresta ao grafo:
GRAFO add_aresta(GRAFO g , VERTICE v1 , VERTICE v2)
{
*(g+v1) =