Árvores

Conteúdo referente à aula de 21 de maio de 2009, por Eduardo.

Árvore geradora mínima

Suponha o seguinte problema: montar uma topologia de rede com custo mínimo, permitindo interconexão entre todos os nós da rede.

Podemos modelar essa situação como um grafo, cujos vértices são roteadores e as arestas uma conexão direta entre dois roteadores, cujo custo de interligação está representando pelo peso. Desejamos apenas as ligações estritamente necessárias, mantendo o custo de instalação da rede o menor possível.

Este é o problema da árvore geradora mínima: dado um grafo, encontrar um conjunto de arestas que configure um árvore, cuja soma dos pesos é mínima.

Algoritmos

A árvore geradora mínima pode ser resolvida através de dois algoritmos gulosos: Kruskal e Prim.

Kruskal

O algoritmo de Kruskal é talvez a forma mais simples de se calcular a árvore geradora mínima. Basta ordernar as arestas por peso, depois processá-las uma a uma em ordem crescente. Farão parte da árvore geradora mínima as arestas que puderem ser adicionadas ao grafo sem gerar ciclos.

Para detectar a geração de ciclos, devemos testar se os dois nós ligados pela aresta pertencem à mesma componente conexa. Para isso, utilizamos uma estrutura de dados auxiliar chamada union-find, que nos permite responder à pergunta "u e v pertencem à mesma componente?" de forma extremamente rápida.

pair<double, pair<int, int> > arestas[1010]; // representa uma aresta... .first = peso e .second = vertices
int m; // numero de arestas
double kruskal() {
    double r = 0.;
    sort(arestas, arestas + m);
    for (int i = 0; i < m; i++) {
        if (unio(arestas[i].second.first, arestas[i].second.second)) r += arestas[i].first;
    }
    return r;
}

Union-find

(voltarei para completar esta seção em breve, mas fiquem à vontade para adiantar o serviço)

Código:

int pai[VERTICES];  // Representa quem é o pai de cada um na floresta de union-find (inicializado com pai[i] = i)
int posto[VERTICES];  // vetor de posto, inicializado com 0
 
int getrep(int x) {
    if (pai[x] != x) pai[x] = getrep(pai[x]);
    return pai[x];
}
 
// "union" é keyword do C/C++, por isso comemos o "n" no final
bool unio(int a, int b) { // retorna true caso a união tenha sido realmente feita... faz a implementação do kruskal ser mais simples
    // atualiza ponteiros para seus representantes
    a = getrep(a);
    b = getrep(b);
    if (a == b) return false; // pertencem à mesma componente, então não pode unir
 
    // faz união
    if (posto[a] >= posto[b]) {
        pai[b] = a;
        if (posto[a] == posto[b]) posto[a]++;
    }
    else pai[a] = b;
    return true;
}

Prim

Diferentemente do Kruskal, cujo estado intermediário pode possuir várias componentes, no Prim garantimos sempre a existência de uma única componente, criada de forma incremental.

Inicialização: Escolha um nó qualquer do grafo, marque-o como visitado e coloque todas as arestas que incidem neste nó em uma heap mínima.

Loop: retire a menos aresta mínima do heap. Caso ambas as extremidades da aresta sejam nós visitados, esta aresta produz um ciclo, devendo ser descartada e reiniciando o loop. Do contrário, adicione a aresta à árvore geradora mínima, marque o nó adicionado à componente como visitado (repare que para a aresta existir no heap, uma de suas extremidades já havia sido visitada) e adicione as arestas incidentes neste nó ao heap, reiniciando o loop.

Condição de parada: Todos os N nós estão marcados como visitados, ou o heap se encontra vazio.

// Implementação do Prim em O(N²) (não usa heap)
// TODO: implementar com heap... eh ainda mais facil
#define INF 0x3F3F3F3F
 
int grafo[1010][1010], dist[1010];
bool marca[1010];
int N;
 
int Prim() {
    int ans = 0; // tamanho da MST (soma das arestas)
    int cur, cont;
    memset(marca, 0, sizeof(marca));
    memset(dist, INF, sizeof(dist));
    cur = 1; // Nó corrente
    cont = 1; // Contador de quantos nós já analisou
    // Enquanto não analisou todos os nós do grafo
    while (cont < N) {
        marca[cur] = 1;
        int menor = INF, indice = -1;
        // Percorre todos os nós não visitados procurando pelo que tem a
        // menor distância para a árvore.
        for (int i = 1; i <= N; i++) if (!marca[i]) {
            // Atualiza vetor de distancia do nó
            if (grafo[cur][i] < dist[i])
                dist[i] = grafo[cur][i];
            // Verifica se a distância para este nó é a menor
            if (dist[i] < menor) {
                menor = dist[i];
                indice = i;
            }
        }
        // Se o grafo não é conexo não vai analisar todos os nós.
        // Então pára quando não achar mais nenhum para visitar.
        if (indice == -1) break;
 
        cont++;
        ans += menor;
        cur = indice;
    }
    return ans;
}

Comer folhas (Programação Dinâmica)

(voltarei para completar esta seção em breve, mas fiquem à vontade para adiantar o serviço)

Problemas / Exercícios

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License