INF1010 3WB – T6: Uma aplicação de partições dinâmicas em grafos: algoritmo de Kruskal.

Enunciado:

Implemente uma classe UnionFind em C++, com a interface mostrada no arquivo t6_unionfind.h abaixo.

1. Modifique a sua classe Grafo para incluir a função kruskal(), conforme mostrado no arquivo t6_grafo_kruskal.h abaixo.
2. Implemente a função kruskal() de forma que ela retorne um Grafo que corresponde à árvore geradora mínima resultante deste algoritmo. Utilize a sua classe UnionFind nessa implementação.
3. Nas duas classes, é permitido criar funções ou variáveis membro privadas, para facilitar a implementação.
4. Casos de teste.

t6_unionfind.h

#ifndef T6_UNIONFIND_H
#define T6_UNIONFIND_H

#include <vector>

class UnionFind
{
public:
    //Inicializa a UnionFind com o numero de elementos
    UnionFind(int n);

    //Destrutor
    ~UnionFind();

    //Retorna a raiz do conjunto a que u pertence
    int buscar(int u);

    //Une os dois conjuntos que contém u e v
    void unir(int u, int v);

    //Retorna o numero de conjuntos diferentes
    int numeroConjuntos();

private:
    std::vector pai;
    std::vector tamanho;
    int numConjuntos;
};

#endif // T6_UNIONFIND_H

t6_grafo_kruskal.h

#ifndef T6_GRAFO_KRUSKAL_H
#define T6_GRAFO_KRUSKAL_H

#include 
class Grafo
{
public:
    //Construtor. N = numero de vertices.
    Grafo( int N );

    //Insere uma aresta no grafo, do nó @de para o nó @para, com peso @peso.
    //Caso @direcionado esteja marcado como false, insere a aresta tambem no sentido para->de
    void insereAresta( int de, int para, int peso = 1, bool direcionado = false );

    //Imprime os vertices e seus vizinhos
    void mostra();

    //Imprime os nos do grafo na ordem de uma busca em largura
    void bfs( int s );

    //Imprime os nos do grafo na ordem de uma busca em profundidade
    void dfs(int s);

    //Retorna a árvore geradora mínima obtida com o algoritmo de Kruskal
    Grafo kruskal();

private:
    struct Aresta
    {
        int v; //Vertice destino
        int p; //Peso da aresta
    };

    enum Cor
    {
        BRANCO,
        CINZA,
        PRETO
    };

    //Lista de adjacencias
    std::vector< std::vector< Aresta > > G;
};

#endif // T6_GRAFO_KRUSKAL_H