Árvores Abrangentes de Menor Custo

Comecemos por verificar que só podemos chegar à MST do circuito caso este seja ligado - isto é, se para cada par de pins existe um caminho que os liga. Caso seja, podemos afirmar que a MST corresponde a um subconjunto $T \subseteq E$ de arcos que formam um circuito ligado com custo minimizado:

Podemos ainda notar que $T$ é acíclico (caso tivesse ciclos, podíamos sempre cortar pelo menos um dos arcos e obter um custo menor - não seria de custo mínimo) e que tem $|V| - 1$ arcos, claro - tendo 3 vértices, idealmente vamos ligá-los com 2 arcos, 6 vértices com 5 arcos, ..., $n$ vértices com $n - 1$ arcos.

Nesta secção, serão abordados dois algoritmos que podem ser utilizados para encontrar a MST de um grafo, ambos partindo de uma abordagem greedy e com complexidade temporal $O(E \log V)$.

Ambos os algoritmos procuram formar gradualmente um conjunto $A$ de arcos, que no fim corresponde a uma MST de $G$.

Será útil definir algumas coisas que nos irão ajudar nas provas dos algoritmos.

Algoritmo de Prim

Observando o comportamento de algoritmo de Prim, podemos ser relembrados do comportamento do algoritmo de Dijkstra. Começamos num qualquer vértice de $G$, e exploramos todos os seus arcos. O arco de menor peso que o liga a um vértice por explorar é adicionado à MST, e fazemos o mesmo para o próximo vértice por explorar com menor distância à MST (esta noção de distância ficará mais clara mais abaixo). Esta abordagem repete-se $|V|$ vezes, terminando com todos os arcos de $G$ explorados. Podemos, claro, reparar que a escolha greedy consiste em escolher sempre o arco de menor peso que sai do vértice que estamos a explorar.

Olhando para o pseudo-código abaixo, podemos notar que o algoritmo guarda o predecessor de cada vértice, pi, bem como o peso do arco que o liga à MST já calculada, distance.

Prim(G, r) // r = vértice inicial
  for each vertex v in G.V
    v.distance = inf
    v.pi = nil
  r.distance = 0
  r.pi = nil
  Q = new MinPriorityQueue(G.V) // queue com prioridade = distancia
  // implícito: A é mantido, sendo adicionado cada vértice gradualmente
  while (!Q.empty())
    u = Q.extractMin()
    for each edge (u, v) in G.adj(u)
      if (v in Q && w(u, v) < v.distance)
        v.pi = u
        v.distance = w(u, v)
        // implícito - Q.decreaseKey(v)

A complexidade temporal do algoritmo é, em geral, $O((V + E) \log V)$. Contudo, como $G$ é necessariamente ligado, $|E| > |V|$, pelo que podemos afirmar (ainda que com a perda de algum rigor) que a complexidade temporal do algoritmo é $O(E \log V)$. A complexidade é esta, visto que:

• Inicialização de pi e distance: $\Theta(V)$

• Inicialização da Min Priority Queue: $O(V)$

O ciclo while é percorrido $\Theta(V)$ vezes, com operação extractMin a levar $O(\log V)$ tempo. Todas as arestas são percorridas durante o decorrer do algoritmo $O(E)$, e a operação implícita de atualização da queue leva $O(\log V)$ tempo. Assim sendo, podemos afirmar que, no total, a complexidade temporal do algoritmo é $O((V + E) \log V)$.

Algoritmo de Kruskal

O algoritmo de Kruskal, já abordado em Matemática Discreta, é também bastante simples. É mantido um conjunto, $S$, inicialmente com $|V|$ árvores (uma por vértice). Cada árvore corresponde a um conjunto disjunto, um set, sem elementos repetidos. $E$ é inicialmente ordenado por ordem crescente de peso dos seus arcos e, seguindo essa mesma ordem, o algoritmo percorre todas as arestas de $E$. A cada momento, é escolhida uma aresta $(u, v)$, e é verificado se atualmente $u$ e $v$ pertencem a árvores diferentes em $S$ - se sim, as respetivas árvores são unidas (de modo disjunto, mantendo a propriedade de set), e a aresta é adicionada à MST. Caso contrário, nada acontece.

Temos que o pseudo-código do algoritmo é:

Kruskal(G, w)
  A = {}
  for each vertex v in G.V
    makeSet(v)
  sort G.E by w
  for each edge (u, v) in G.E
    if findSet(u) != findSet(v)
      union(u, v)
      A = A U {(u, v)}

A escolha greedy aqui é, claro, a escolha do arco de menor peso possível de entre as que ainda não foram exploradas.

O algoritmo tem complexidade temporal $O(E \log V)$. Dissecando-o em pormenor, temos que:

• Realizamos $\Theta(V)$ operações de makeSet (com complexidade $O(1)$)

• Ordenados o conjunto $E$ por ordem crescente de peso, operação que leva $O(E \log E)$ tempo

São realizadas $O(E)$ operações de findSet e union. Recorrendo às estruturas de dados certas*, podemos afirmar que a complexidade temporal do for loop é de $O(E \cdot\alpha(V))$, onde $\alpha(V)$ é uma função de crescimento prolongado (sub-logarítmico). Visto que $E < V^2$, temos necessariamente que $\log E = O(\log V)$, e que o algoritmo tem complexidade temporal $O(E \log V)$.

* As estruturas referidas podem ser encontradas mais abaixo. São utilizadas, para além do algoritmo de Kruskal, no algoritmo de Tarjan para encontrar $LCAs$ (lowest common ancestors).

Estruturas de Dados para Conjuntos Disjuntos

Na secção imediatamente acima, foi referido que a complexidade do algoritmo de Kruskal poderia ser drasticamente reduzida caso se recorresse às estruturas de dados certas.

Inventada em meados dos anos 60, a estrutura Union-Find responde precisamente a este problema em tempo ótimo. Foi descrita pela primeira vez por Bernard Galler e Michael Fischer, num artigo para o Journal of the ACM, e passada cerca de uma década Robert Tarjan (inventor, entre outros, do algoritmo que estudámos para encontrar SCCs) provou que a complexidade temporal do algoritmo de união de conjuntos da estrutura era majorada por $O(m \cdot \alpha(n))$, onde $\alpha$ corresponde à inversa da função de Ackermann, sub-logarítmica.

A estrutura em questão mantém uma coleção de conjunto disjuntos dinâmicos, $S$, onde cada conjunto é representado por um dos seus membros. É, aqui, relevante que o representante seja o mesmo em qualquer momento do algoritmo - isto é, que um pedido do representante de um conjunto seja determinístico para esse conjunto. Precisaremos de suportar três operações principais para a manipulação da estrutura:

• makeSet(x): cria um conjunto disjunto com um único membro, membro esse que, claro, fica como seu representante. Insere este novo conjunto em $S$.

• findSet(x): retorna o representante do conjunto que contém o membro x.

• union(x, y): une os conjuntos que contêm os membros x e y. A implementação abordada em aula leva a que o representante deste novo conjunto seja ou o representante do anterior conjunto de x ou do de y. Os dois conjuntos, agora irrelevantes, são removidos de $S$.

A estrutura em si possui várias implementações internas. Iremos nesta secção apenas abordar a implementação utilizada no algoritmo de Kruskal, que recorre à noção de floresta - $S$ é, aqui, uma floresta de conjuntos disjuntos, onde cada um dos seus conjuntos corresponde a uma árvore n-ária. A raiz de cada árvore tem-se a si própria como pai, e corresponde ao representante do conjunto em que está. Abaixo encontram-se exemplos de árvores que podem representar conjuntos disjuntos nesta implementação:

À esquerda, podemos observar duas árvores de um hipotético conjunto $S$; à direita, o resultado da união dos dois conjuntos. Parece então correto introduzir agora a implementação (ainda não ótima) da estrutura com árvores:

• makeSet(x): cria uma árvore cujo único vértice é x, sendo ele o seu próprio antecessor.

• findSet(x): percorre os antecessores de x até encontrar o representante do conjunto em que se encontra.

• union(x, y): a raiz de uma das árvores passa a apontar para a raiz da outra (observável na figura acima).

Em relação à complexidade temporal, contudo, estamos longe do ideal - $n$ chamadas a union podem levar à criação de uma árvore linear de $n$ nós em cadeia, algo que não queremos (a operação findSet levaria até $n$ subidas pela árvore, por exemplo). Podemos, claro, melhorá-la, e vamos fazê-lo seguindo um par de heurísticas:

Postas estas duas heurísticas em prática, o pseudo-código das operações será:

makeSet(x)
  parent[x] = x
  rank[x] = 0

findSet(x)
  if parent[x] != x
    parent[x] = findSet(parent[x])
  return parent[x]

union(x, y)
  link(findSet(x), findSet(y))

link(x, y)
  if rank[x] > rank[y]
    parent[y] = x
  else
    parent[x] = y
    if rank[x] == rank[y]
      rank[y]++

Podemos notar que o próprio union chama, por definição, findSet, produzindo assim resultados mais eficientes para várias chamadas sucessivas.

A execução de $m$ operações levará, então, $O(m \cdot \alpha(n))$ tempo. Visto que para qualquer aplicação concebível para a estrutura o número de árvores iniciais é menor que $10^{80}$, podemos considerar $\alpha(n) \leq 4$ (a prova encontra-se nos slides), pelo que podemos até considerar o algoritmo linear para o número de operações requeridas. Resta notar que apenas utilizando a união por categoria (sem compressão de caminhos), a complexidade seria $O(m \cdot \log n)$, já assim bastante melhor que a original $O(mn)$.

• Notas Kruskal, Prim - Prof. José Fragoso
• Notas Kruskal, Union-Find - Prof. José Fragoso