INF1010 - Mais Grafos - Árvore geradora de custo mínimo

entrega: até quinta, dia 20/6, às 23h

No laboratório de hoje vamos implementar a função arvoreCustoMinimo usando o algoritmo de Kruskal visto em sala. Por favor leia com atenção o resto desse texto antes de começar sua implementação.

O arquivo grafo.c contém um esboço da implementação de grafos, já vista nos labs anteriores, para implementação da função arvoreCustoMinimo. A interface está em grafo.h e os arquivos grafo1.dat, grafo2.dat grafo3.dat e contêm dois exemplos de grafos no formato esperado.

A função recebe como entrada o arquivo com a descrição do grafo, no mesmo formato já visto, e retorna um ponteiro para um grafo que é a árvore de custo minimo calculada. Em seu programa de teste, lembre-se de que vc pode usar a função grafoMostra para conferir o grafo gerado.

Para calcular a árvore de custo mínimo, a função deve utilizar um heap para armazenar todas as arestas do grafo, usando o peso como prioridade, e ir retirando-as do heap uma a uma para criar a árvore. A "árvore" é um novo grafo, criado pela função. Utilize a função já disponível criaViz para acrescentar uma aresta a cada um dos nós em suas extremidades.

Para verificar se uma aresta une duas componentes ainda não conexas, vc deve utilizar uma estrutura de união e busca. Inicialmente, essa estrutura representará uma partição cheia de "conjuntos unitários", com cada nó em uma parte sepadada. A medida que vc inserir arestas no grafo, vc deve fazer a união de partes em sua partição.

As estruturas de heap e de união e busca necessário estão dadas nos seguintes arquivos (Não modifique esses arquivos por favor!):

1. ub.h
2. ub.c
3. listaprio.h (Observe que a interface do heap mudou novamente para permitir a manipulação das arestas! Agora cada elemento do heap armazena os dois nós associados a uma aresta, além de seu peso, e a função listap_remove retorna esses dois nós através de endereços passados para ela.)
4. listaprio.c

e há um arquivo de teste em testek.c. Para compilar, lembre-se de passar todos os arquivos utilizados:

gcc -Wall -o testek testek.c ub.c listaprio.c grafo.c 

Para usar esse teste, passe o nome do arquivo com a descrição do grafo pela linha de comando, escrevendo por exemplo:

./testek grafo1.dat

Entregue apenas o arquivo grafo.c.

Peço encarecidamente que não mudem os nomes dados! E garantam que seus programas compilem em ambiente linux.