Este projeto implementa uma estrutura de dados de grafo utilizando listas de adjacência na linguagem de programação C. A estrutura é genérica e pode ser utilizada para representar grafos direcionados ou não direcionados. Além disso, o projeto inclui uma série de interfaces para manipulação de pilhas, vértices e visualização de grafos.
Grafos são estruturas de dados que modelam a relação entre pares de objetos. Cada objeto é chamado de vértice e a relação entre eles é chamada de aresta. Grafos são utilizados em diversas áreas da ciência da computação, como redes de computadores, análise de redes sociais, algoritmos de roteamento e muito mais.
A representação do grafo é feita através de um vetor de listas de adjacência, onde cada lista encadeada está associada a um vértice do grafo e contém todos os seus vizinhos. Esta representação é eficiente em termos de espaço, ocupando O(n + m) onde n é o número de vértices e m é o número de arestas.
- A representação do grafo não é única, pois as listas podem variar na ordem dos elementos.
- Determinar a existência de uma aresta incidente a um vértice tem custo O(n) para grafos densos.
- Espaço ocupado é proporcional a O(n + m).
O código é genérico e utiliza interfaces como stack, vertex, e print_graph para manipulação do grafo.
A interface vertex é flexível e adaptável para acomodar diferentes tipos de dados de vértices em um grafo.
vertex_print: Imprime os detalhes de um vértice.vertex_match: Compara dois vértices para checar se são idênticos.vertex_comparison_weights: Avalia os pesos de dois vértices, útil em grafos ponderados.vertex_destroy: Libera a memória alocada para um vértice.
Certifique-se de que você tem o compilador gcc para C e o interpretador python instalados em seu sistema.
- Abra um terminal na pasta do projeto.
- Execute o script de compilação com o seguinte comando:
sh run.shEste script irá compilar todos os arquivos de código-fonte C e gerar um executável.
Observação para usuários de Linux/Mac: Ao executar o script
run.sh, utilize./runem vez de./run.exe.
Para gerar um novo grafo utilizando o script Python incluído:
Execute o seguinte comando, substituindo 100 pelo número de vértices e 500 pelo número de arestas que deseja no grafo:
python tools/generate_graph.py 100 500 data/graph.txtIsso criará um arquivo graph.txt no diretório data com a representação de um grafo gerado aleatoriamente.
Para remover os arquivos compilados e limpar o diretório de trabalho, você pode usar:
sh clean.sh