beecrowd Raquel Marcolino

Árvore Geradora de Custo Mínimo

Dado um grafo conexo, determine um sub grafo conexo deste grafo tal que a soma de suas arestas seja a mínima possível.

Descrição

Para qualquer grafo conexo, sabemos que existe um sub grafo tal que possa conectar todos os seus vértices com arestas existentes de modo que o custo das arestas seja o mínimo. A esse sub grafo damos o nome de árvore geradora de custo mínimo. Tal grafo é uma árvore pois usa o número mínimo de arestas para que todos os vértices permaneçam unidos (|V| - 1), mas escolhe as melhores arestas a fim de garantir que o custo seja o mínimo possível.

Existem dois algoritmos famosos na literatura para resolver este problema, o algoritmo de Kruskal e o de Prim. Aqui apresentamos os dois algoritmos com detalhes, mostrando suas respectivas complexidades e implementações.

Algoritmo de Kruskal

Complexidades

Termo assintótico

Tempo

O(|E| log |V|)

Espaço

O(|E| + |V|)

A ideia do algoritmo de Kruskal é reunir todas as arestas e tentar selecioná-las gulosamente, ou seja, tentando escolher sempre as menores arestas sempre que possível. Compreensivamente em forma de lista, temos aqui os passos que o algoritmo de Kruskal precisa executar

  1. Coletar todas as arestas do grafo e ordená-las da aresta de menor custo para a de maior custo;

  2. Para cada aresta, em ordem, verificar se tal aresta não irá conectar dois vértices da mesma sub árvore. Se conectar, tal aresta é descartada, caso contrário, a aresta entra na solução do algoritmo.

As figuras abaixo apresentam o algoritmo de Kruskal funcionando na prática, onde cada aresta em vermelho representa a aresta a ser analisada e arestas em verde representam arestas que foram aceitas como solução, ou seja, arestas que formam a árvore geradora de custo mínimo.

Figuras em breve, peço perdão pelo inconveniente.

A ordenação é feita em O(|E| log |E|), que no caso de um grafo completo onde |E| é aproximadamente |V|², temos que O(|E| log |V|²) = O(2 |E| log |E|) = O(|E| log |E|).

Já para a verificação se uma aresta não irá conectar dois vértices pertences à mesma sub árvore, usamos uma estrutura de dados chamada UnionFind capaz de verificar e atualizar em tempo constante a qual sub árvore cada vértice pertence. Com isso, a complexidade para esse trecho é de O(|E|), pois é preciso fazer tal verificação para todas as arestas existentes.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<vector<pair<int, int> > > grafo;
vector<pair<int, pair<int, int> > > arestas;

class UnionFind{
    private:
    vector<int> conjunto, rank;

    public:
    UnionFind(int N){
        rank.assign(N, 0);
        conjunto.assign(N, 0);
        for(int i = 0; i < N; ++i){
            conjunto[i] = i;
        }
    }

    int findSet(int i){
        return (conjunto[i] == i) ? i : (conjunto[i] = findSet(conjunto[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    void unionSet(int i, int j){
        if(!isSameSet(i, j)){
            int x = findSet(i);
            int y = findSet(j);

            if(rank[x] > rank[y]){
                conjunto[y] = x;
            }else{
                conjunto[x] = y;
                if(rank[x] == rank[y]){
                    rank[y]++;
                }
            }
        }
    }
};

int Kruskal(int n, int m){
    UnionFind UF(n);
    int custo = 0;

    sort(arestas.begin(), arestas.end());

    for(int i = 0; i < m; ++i){
        pair<int, pair<int, int> > aresta = arestas[i];
        
        if(!UF.isSameSet(aresta.second.first, aresta.second.second)){
            custo += aresta.first;
            UF.unionSet(aresta.second.first, aresta.second.second);
        }
    }

    return custo;
}

int main(){
    int V, E, a, b, peso, custo;

    cin >> V >> E;
    grafo.assign(V, vector<pair<int, int> >());
    for(int i = 0; i < E; ++i){
        cin >> a >> b >> peso;
        grafo[a].push_back(pair<int, int>(b, peso));
        grafo[b].push_back(pair<int, int>(a, peso));
        arestas.push_back(pair<int, pair<int, int> >(peso, pair<int, int>(a, b)));
    }

    cout << Kruskal(V, E) << endl;

    return 0;
}

Algoritmo de Prim

Complexidades

Termo assintótico

Tempo

O(|E| log |V|)

Espaço

O(|E| + |V|)

Enquanto o algoritmo de Kruskal é focado nas arestas, o algoritmo de Prim foca nos vértices. Escolhendo um vértice inicial (que pode ser qualquer um, já que todos os vértices fazem parte da árvore geradora de custo mínimo), as arestas que começam a ser consideradas são as incidentes a esse vértice e a partir daí, ir selecionando também gulosamente quais arestas podem fazer parte da árvore, com a diferença de que como apenas uma árvore é formada, em vez de sub árvores, então não precisamos do Union Find, um simples vetor de booleanos basta para verificar se dois vértices estão na árvore ou não. Uma vez que uma aresta é aceita, as arestas incidentes ao novo vértice entrando na árvore são colocadas também para serem levadas em consideração, se isso já não tiver ocorrido. Compreensivamente em forma de lista, temos aqui os passos que o algoritmo de Prim precisa executar

  1. Coletar as arestas do grafo incidentes a um vértice inicial qualquer;

  2. Para cada aresta, da ordem da menor para maior, inseri-la na resposta se ela não se conecta com um vértice que já está na árvore;

  3. Colocar todas as arestas incidentes ao vértice novo na árvore;

  4. Ir repetindo o processo de escolher arestas e inserir novas arestas até que a árvore seja montada;

As figuras abaixo representam o algoritmo de Prim funcionando na prática, onde cada aresta em vermelho representa a aresta a ser analisada e arestas em verde representam arestas que foram aceitas como solução, ou seja, arestas que formam a árvore geradora de custo mínimo.

Figuras em breve, peço perdão pelo inconveniente.

Cada aresta é incluída em uma fila de prioridade, cuja complexidade de inserção é de O(log n). Como queremos inserir |E| arestas, então a complexidade para essas inserções é de O(|E| log |E|). Verificar se um vértice está ou não na árvore é constante, logo, a complexidade total continua sendo de O(|E| log |E|).

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<bool> visitado;
vector<vector<pair<int, int> > > grafo;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > fila;

void processa(int u){
    visitado[u] = true;

    for(int i = 0; i < grafo[u].size(); ++i){
        pair<int, int> par = grafo[u][i];
        int v = par.first;
        int d = par.second;

        if(!visitado[v])    fila.push(pair<int, int>(d, v));
    }
}

int main(){
    int E, V, a, b, peso, custo;

    cin >> V >> E;
    grafo.assign(V, vector<pair<int, int> >());
    for(int i = 0; i < E; ++i){
        cin >> a >> b >> peso;
        grafo[a].push_back(pair<int, int>(b, peso));
        grafo[b].push_back(pair<int, int>(a, peso));
    }

    visitado.assign(V, false);
    processa(0);
    custo = 0;
    while(!fila.empty()){
        pair<int, int> frente = fila.top();
        fila.pop();

        int d = frente.first;
        int u = frente.second;

        if(!visitado[u]){
            resposta += d;
            processa(u);
        }
    }

    cout << custo << endl;

    return 0;
}

Problemas

Aqui alguns dos problemas que podem ser resolvidos usando um destes algoritmos:

page1552 - Resgate em Queda Livre
PreviousGrafosNextAlgoritmos Raros

Last updated