No laboratório de hoje vamos implementar a função arvoreCustoMinimo usando o algoritmo de Kruskal visto em sala. Leia com atenção todo o enunciado do laboratório antes de começar sua implementação!
O arquivo grafo.c contem a implementação de grafos já vista nos laboratórios anteriores, e o esboço da implementação da função arvoreCustoMinimo. A interface está em grafo.h, e os arquivos grafo1.dat, grafo2.dat e grafo3.dat contêm exemplos de grafos no formato de leitura esperado.
A função arvorecustoMinimo recebe como entrada um arquivo com a descrição de um grafo e retorna um ponteiro para um grafo que é a árvore de custo minimo do grafo de entrada. Em seu programa de teste, lembre-se de que você usar a função grafoMostra para conferir o grafo gerado.
Para calcular a árvore de custo mínimo, a função deve utilizar um min 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 arvoreCustoMinimo 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, você 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. À medida que você inserir arestas no grafo, você 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 no arquivos ub.h, ub.c, heap.h e heap.c
Não modifique esses arquivos por favor!.
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 heap_remove retorna esses dois nós através de endereços passados para ela. Tome cuidado para não inserir a mesma aresta duas vezes, pois ela está representada na lista de vizinhos dos dois vértices correspondentes.
Há também 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 heap.c grafo.cPara 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 (arquivos e funções), nem os protótipos das funções! E garantam que seus programas compilem em ambiente Linux.