Árvore geradora mínima - algoritmo de Prim

Dado um grafo não direcionado e com pesos $G$ com $n$ vértices e $m$ arestas. Você deseja encontrar uma árvore geradora do grafo que conecte todos os vértices e tenha o menor peso (ou seja, a soma dos pesos das arestas é mínima). Uma árvore geradora é um conjunto de arestas nas quais qualquer vértice pode alcançar qualquer outro vértice por exatamente um caminho simples. A árvore geradora com o menor peso é chamada de árvore geradora mínima.

Na imagem da esquerda, um grafo não direcionado com pesos e, na imagem da direita, a árvore geradora mínima correspondente.

Random graph MST of this graph

Qualquer árvore geradora necessariamente conterá $n-1$ arestas.

Esse problema aparece naturalmente em muitos problemas. Por exemplo: existem $n$ cidades e, para cada par de cidades, temos o custo de construir uma estrada entre elas (ou podemos saber que é "fisicamente" impossível construir uma estrada entre elas). Temos que construir estradas, para que possamos ir de cada cidade a outra cidade, e o custo para a construção de todas as estradas deve ser mínimo.

Algoritmo de Prim

Esse algoritmo foi descoberto originalmente pelo matemático tcheco Vojtěch Jarník em 1930. No entanto, esse algoritmo é conhecido principalmente como algoritmo de Prim depois que o matemático americano Robert Clay Prim o redescobriu e republicou em 1957. Além disso, Edsger Dijkstra publicou esse algoritmo em 1959.

Descrição

Aqui, descrevemos o algoritmo em sua forma mais simples. A árvore geradora mínima é construída gradualmente adicionando arestas uma de cada vez. No início, a árvore geradora consiste apenas em um único vértice (escolhido arbitrariamente). Em seguida, a aresta de peso mínimo que sai desse vértice é selecionada e adicionada à árvore geradora. Depois disso, a árvore geradora já consiste de dois vértices. Agora selecione e adicione a aresta com o peso mínimo que tem uma extremidade em um vértice já selecionado (ou seja, um vértice que já faz parte da árvore geradora), e a outra extremidade em um vértice não selecionado. E assim por diante, ou seja, toda vez estaremos selecionando e adicionando a aresta com peso mínimo que conecta um vértice selecionado a um vértice não selecionado. O processo é repetido até que a árvore geradora contenha todos os vértices (ou equivalentemente até que tenhamos $n - 1$ arestas).

No final, a árvore geradora construída será mínima. Se o grafo não era originalmente conexo, então não existe uma árvore de abrangência; portanto, o número de arestas selecionadas será menor que $n - 1$.

Prova

Deixe o grafo $G$ ser conexo, ou seja, deixe a resposta existir. Denotamos por $T$ o grafo resultante encontrado pelo algoritmo de Prim, e por $S$ a árvore geradora mínima. Claro que $T$ será de fato uma árvore geradora e um subgrafo de $G$. Só precisamos mostrar que os pesos de $S$ e $T$ coincidem.

Considere a primeira vez no algoritmo quando adicionamos uma aresta a $T$ que não faz parte de $S$. Vamos denotar essa aresta como $e$, suas extremidade por $a$ e $b$, e o conjunto de vértices já selecionados como $V$ ($a \in V$ e $b \notin V$, ou vice versa).

Na árvore geradora mínima $S$ os vértices $a$ e $b$ são conectados por algum caminho $P$. Nesse caminho, podemos encontrar uma aresta $f$ no qual uma extremidade de $f$ esteja em $V$ e a outra extremidade não. Como o algoritmo escolheu $e$ em vez de $f$, isso significa que o peso de $f$ é maior ou igual ao peso de $e$.

Adicionamos a aresta $e$ à árvore geradora mínima $S$ e removemos a aresta $f$. Ao adicionar $e$ criamos um ciclo e, como $f$ também fazia parte do único ciclo, removendo-o, o grafo resultante fica novamente livre de ciclos. E como removemos apenas uma aresta de um ciclo, o grafo resultante ainda está conectado.

A árvore geradora resultante não pode ter um peso total maior, já que o peso de $e$ não era maior que o peso de $f$, e também não pode ter um peso menor, já que $S$ era uma árvore geradora mínima. Isso significa que, substituindo a aresta $f$ por $e$ geramos uma árvore geradora mínima diferente. E $e$ precisa ter o mesmo peso que $f$.

Assim, todas as arestas que escolhemos no algoritmo de Prim têm os mesmos pesos que as arestas de qualquer árvore geradora mínima, o que significa que o algoritmo de Prim realmente gera uma árvore geradora mínima.

Implementação

A complexidade do algoritmo depende de como procuramos a próxima aresta mínima entre as arestas apropriadas. Existem várias abordagens que levam a diferentes complexidades e diferentes implementações.

Implementações triviais: $O(n m)$ e $O(n^2 + m \log n)$

Se procuramos a aresta iterando sobre todas as arestas possíveis, então irá levar $O(m)$ para encontrar a aresta com o peso mínimo. A complexidade total será de $O(n m)$. Na pior das hipóteses, isso é $O(n^3)$, realmente, bem lento.

Esse algoritmo pode ser aprimorado se observarmos apenas uma aresta de cada vértice já selecionado. Por exemplo, podemos ordenar as arestas de cada vértice em ordem crescente de seus pesos e armazenar um ponteiro para a primeira aresta válida (ou seja, uma aresta que vá para um vértice não selecionado). Depois de encontrar e selecionar a aresta mínima, atualizamos os ponteiros. Isso fornece uma complexidade $O(n^2 + m)$, e, para ordenar as arestas, um adicional de $O(m \log n)$, o que fornece a complexidade $O(n^2 \log n)$ no pior dos casos.

Abaixo, consideramos dois algoritmos ligeiramente diferentes, um para grafos densos e outro para grafos esparsos, ambos com uma complexidade melhor.

Grafos densos: $O(n^2)$

Abordamos esse problema por um lado diferente: para cada vértice ainda não selecionado, armazenaremos a aresta mínima para um vértice já selecionado.

Então, durante uma etapa, precisamos apenas observar essas arestas de peso mínimo, isso irá ter uma complexidade $O(n)$.

Após adicionar uma aresta, alguns ponteiros das arestas mínimas devem ser recalculados. Observe que os pesos apenas podem diminuir, ou seja, a aresta de peso mínimo de todos os vértices ainda não selecionados pode permanecer a mesma ou será atualizada por uma aresta no vértice recém-selecionado. Portanto, essa fase também pode ser realizada em $O(n)$.

Assim, recebemos uma versão do algoritmo de Prim com a complexidade $O(n^2)$.

Em particular, essa implementação é muito conveniente para o problema da Árvore Geradora Mínima Euclidiana: temos $n$ pontos em um plano e a distância entre cada par de pontos é a distância euclidiana entre eles, e queremos encontrar uma árvore geradora mínima para esse grafo completo. Esta tarefa pode ser resolvida pelo algoritmo descrito em tempo $O(n^2)$ e com $O(n)$ de memória, o que não é possível com o algoritmo de Kruskal.

int n;
vector<vector<int>> adj; // matriz de adjacência - grafo
const int INF = 1000000000; // peso INF significa que não existe aresta

struct Edge {
    int w = INF, to = -1;
};

void prim() {
    int total_weight = 0;
    vector<bool> selected(n, false);
    vector<Edge> min_e(n);
    min_e[0].w = 0;

    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j = 0; j < n; ++j) {
            if (!selected[j] && (v == -1 || min_e[j].w < min_e[v].w))
                v = j;
        }

        if (min_e[v].w == INF) {
            cout << "Sem MST!" << endl;
            exit(0);
        }

        selected[v] = true;
        total_weight += min_e[v].w;
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;

        for (int to = 0; to < n; ++to) {
            if (adj[v][to] < min_e[to].w)
                min_e[to] = {adj[v][to], v};
        }
    }

    cout << total_weight << endl;
}

A matriz de adjacência adj[][] de tamanho $n \times n$ armazena os pesos das arestas e usa o peso INF se não existir uma aresta entre dois vértices. O algoritmo usa duas arrays: o sinalizador selected[], que indica quais vértices já foram selecionados, e a array min_e[] que armazena a aresta com peso mínimo em um vértice selecionado para cada vértice ainda não selecionado (ele armazena o peso e vértice final). O algoritmo executa $n$ etapas, em cada iteração o vértice com a aresta de menor peso é selecionado e o min_e[] de todos os outros vértices é atualizado.

Grafos esparsos: $O(m \log n)$

No algoritmo descrito acima, é possível interpretar as operações de encontrar o mínimo e modificar alguns valores como operações em conjunto. Essas duas operações clássicas são suportadas por muitas estruturas de dados, por exemplo: set no C++ (que são implementadas por meio de árvores rubro-negras).

O algoritmo principal permanece o mesmo, mas agora podemos encontrar a aresta mínima em $O(\log n)$. Por outro lado, o recálculo dos ponteiros agora levará $O(n \log n)$, o que é pior do que no algoritmo anterior.

Mas quando consideramos que precisamos apenas atualizar $O(m)$ vezes no total e performar $O(n)$ buscas pela aresta mínima, então a complexidade total será $O(m \log n)$. Para grafos esparsos isso é melhor que o algoritmo acima mas, para grafos densos, isso será mais lento.

const int INF = 1000000000;

struct Edge {
    int w = INF, to = -1;
    bool operator<(Edge const& other) const {
        return make_pair(w, to) < make_pair(other.w, other.to);
    }
};

int n;
vector<vector<Edge>> adj;

void prim() {
    int total_weight = 0;
    vector<Edge> min_e(n);
    min_e[0].w = 0;
    set<Edge> q;
    q.insert({0, 0});
    vector<bool> selected(n, false);
    for (int i = 0; i < n; ++i) {
        if (q.empty()) {
            cout << "Sem MST!" << endl;
            exit(0);
        }

        int v = q.begin()->to;
        selected[v] = true;
        total_weight += q.begin()->w;
        q.erase(q.begin());

        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;

        for (Edge e : adj[v]) {
            if (!selected[e.to] && e.w < min_e[e.to].w) {
                q.erase({min_e[e.to].w, e.to});
                min_e[e.to] = {e.w, v};
                q.insert({e.w, e.to});
            }
        }
    }

    cout << total_weight << endl;
}

Aqui o grafo é representado por meio de uma lista de adjacência adj[], onde adj[v] contém todas as arestas (na forma de pares de peso e alvo) para o vértice v. min_e[v] armazenará o peso da menor aresta do vértice v para um vértice já selecionado (novamente na forma de um par de peso e alvo/destino). Além disso, a queue q é preenchida com todos os vértices ainda não selecionados na ordem crescente de peso min_e. O algoritmo executa n etapas, em cada uma seleciona o vértice v com o menor peso min_e (extraindo-o do início da queue) e, em seguida, examina todas as arestas desse vértice e atualiza os valores em min_e (durante uma atualização precisamos remover a antiga aresta da queue q e colocar a nova aresta).

Problemas