Listas de adjacência

Nesta representação as n linhas da matriz de adjacência são representadas como n listas encadeadas. Existe uma lista para cada vértice em G. Os nós na lista i representam os vértices que são adjacentes ao vértice i.

Cada nó na lista possui pelo menos dois campos: VÉRTICE, que armazena o indice do vértice que é adjacente i e NEXT, que é um ponteiro para o próximo nó adjacente. As cabeças das listas podem ser armazenas em um array de ponteiros para facilitar o acesso aos vértices. É conveniente armazenarmos em cada entrada do array de cabeças de listas um campo FLAG que será utilizado posteriormente para indicar se um dado vértice possui alguma propriedade, por exemplo em buscas, este FLAG pode indicar se um dado vértice já foi visitado ou não.

typedef struct no;
typedef struct heads;

struct nos{
    int VERTEX;
    no *NEXT;
};

struct heads{
    int FLAG;
    no *ADJ;
};

/* aloca o array de heads para um grafo com
NUMNOS v\'ertices */

G = (heads *) malloc(NUMVERT*sizeof(head));

No caso de um grafo não dirigido com n vértices e e arestas, a representação acima requer um array de tamanho n para as cabeças e 2e nós nas listas. O grau de qualquer vértice i em um grafo não dirigido pode ser determinado pelo número de nós na lista do vértice i. O número total de arestas no grafo pode ser determinado em tempo O(n+e).

No caso de dígrafos, o número total de nós nas listas é e. O grau de saída de um nó i é o número de nós na lista do vértice i. O grau de entrada de um vértice i pode ser calculado em tempo O(n+e) (como este cálculo pode ser feito?).