Lista de Adjacências em C

Se você for trabalhar com algoritmos em grafos não é possível sem lista de adjacências ou matriz de adjacências para representar os grafos. Vou tratar aqui da lista de adjacências pois foi a forma que mais usei até o meu estado atual na faculdade.

No meu caso foi implementado uma lista de adjacências para um grafo não-dirigido, ou seja, a aresta (a b) é a mesma que (b a). Uma lista de adjacência nada mais é que um vetor de listas encadeadas, ou listas encadeadas de listas encadeadas. No meu caso utilizei vetor de listas encadeadas pois eu já sei qual é o maior vértice do meu grafo, dessa forma posso declarar o tamanho do meu vetor como sendo o maior vértice do meu grafo. Caso não se conheça o maior vértice do grafo, pode ser feito a implementação com listas encadeadas de listas encadeadas, onde as arestas vão sendo inseridas até que o arquivo chegue no final, sem uma limitação.

Os índices do meu vetor correspondem aos vértices do grafo, o que guardo nesses vetores são os graus dos vértices e a lista encadeada a cada índice do vetor são os vértices adjacentes à ele.

Por exemplo, um grafo e sua lista de adjacências:
Implementei um algoritmo em C que monta a lista de adjacências de um dado grafo, vale lembrar que a entrada é um arquivo onde o mesmo deve conter pares de arestas do grafo que se deseja montar, por exemplo para o grafo da figura acima o arquivo de entrada do algoritmo seria:

1 2
1 3
2 4
2 5
3 4
4 5
4 6
6 7
6 8
7 8

O Algoritmo: (bastar compilar utilizando o gcc (gcc algoritmo.c -o nome qlq) e mandar o arquivo como entrada ./nome qlq Input).
Mudamos no algoritmo o define para 8, pois conhecemos o valor do maior vértice do grafo.

Link para o algoritmo

Saída ao executar o algoritmo:

1: (2) ==>2 3
2: (3) ==>1 4 5
3: (2) ==>1 4
4: (4) ==>2 3 5 6
5: (2) ==>2 4
6: (3) ==>4 7 8
7: (2) ==>6 8
8: (2) ==>6 7

Posted in: