Árvores Abrangentes de Menor Custo

Motivação

O Sr. Johnson está a prototipar um novo design para um circuito elétrico. Um circuito é composto por um set de pins e por um conjunto de fios que os interliga. Para poder vender o seu circuito a um preço mais baixo que os da concorrência, precisa de cortar custos, e, como tal, opta por procurar o conjunto de fios tal que consegue interligar todos os pins de modo mais barato. Cada possível ligação tem um custo associado, claro - o circuito tem desníveis e indireções que fazem com que o custo real do fio não seja uniforme para ligar quaisquer dois pins. Para encontrar o custo ótimo, recorre a um algoritmo que calcula a árvore abrangente de menor custo do circuito, minimum spanning tree (MST), um grafo não dirigido onde cada vértice corresponde a um pin e onde as possíveis ligações (fios) entre estes correspondem a arcos pesados.

As MST's são, então, geralmente utilizadas para encontrar as soluções mais baratas para interligar um conjunto de vértices - interligar pins num circuito, redes de telecomunicação, de gás natural, estradas, entre outras.

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 TET \subseteq E de arcos que formam um circuito ligado com custo minimizado:

minw(T)=(u,v)Tw(u,v)\min w(T) = \sum_{(u, v) \in T} w(u, v)

Podemos ainda notar que TT é 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 V1|V| - 1 arcos, claro - tendo 3 vértices, idealmente vamos ligá-los com 2 arcos, 6 vértices com 5 arcos, ..., nn vértices com n1n - 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(ElogV)O(E \log V).

Ambos os algoritmos procuram formar gradualmente um conjunto AA de arcos, que no fim corresponde a uma MST de GG.

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

Corte

Temos que um corte (S,VS)(S, V - S) de um grafo corresponde a uma partição do conjunto de vértices do mesmo. A figura abaixo exemplifica-o: os vértices acima do corte correspondem a SS e os abaixo a VSV - S.

Um arco cruza um corte caso um dos seus vértices se encontre em SS e o outro em VSV - S. Mais ainda, o mesmo diz-se leve caso, de entre todos os arcos que cruzam o corte, este tenha peso mínimo. Por fim, temos que um conjunto AA respeita um corte caso nenhum dos seus arcos cruze o corte.

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 GG, 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|V| vezes, terminando com todos os arcos de GG 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)
Exemplo da aplicação do algoritmo

O grafo abaixo considera aa como vértice inicial, e já tem o primeiro passo de Prim realizado (explorou todos os arcos que dele saem, atualizando os pais e distâncias à MST).

Podemos notar que, dos vértices por explorar, bb é o que tem menor key (distância à MST), pelo que o escolhemos. Repetimos o processo, tal que:

Como ficou claro acima, não vamos mantendo a soma de um vértice à raiz, mas sim ao vértice que o liga à MST. Por exemplo, ao explorar o arco (b,c)(b, c), a distância de cc foi atualizada para 88, e não para 4+8=124 + 8 = 12.

O processo acaba por ser bastante intuitivo, pelo que de seguida encontram-se todos os restantes passos da aplicação do algoritmo ao grafo:

(Podemos notar que o passo abaixo não tem arestas a verde, já que todas as arestas de HH já foram exploradas.)

A MST resultante será, então:

Prova da escolha ser ótima e funcionar

Seja GG um grafo, TT a árvore que o algoritmo de Prim retorna e SS uma outra MST.

Consideremos a primeira vez em que o algoritmo não escolhe uma aresta que esteja no conjunto de vértices já selecionados - seja ela (u,v)(u, v). Temos, claro, que um dos vértices do arco pertence a TT e outro não. Como a MST tem de ser um grafo ligado, se SS não contém (u,v)(u, v), terá necessariamente de conter um caminho p=(u,...,v)p = (u, ..., v). Ao passar pelo caminho, teremos necessariamente de encontrar um arco em que um vértice esteja no conjunto de vértices já selecionados e outro que não, caso contrário o algoritmo nunca iria escolher (u,v)(u, v). Seja esse arco (x,y)(x, y). Já que ambos os arcos cruzam o corte atual e o algoritmo escolheu (u,v)(u, v), então temos necessariamente que w(u,v)w(x,y)w(u, v) \leq w(x, y). Podemos ainda notar que a união dos arcos de pp com (u,v)(u, v) forma um ciclo, e que tanto a remoção de (u,v)(u, v) como a de (x,y)(x, y) quebram-no. Ora, temos que a remoção de (x,y)(x, y) a pp e posterior junção de (u,v)(u, v) ao mesmo levará a um conjunto com peso menor ou igual ao de pp original, já que, como visto anteriormente, w(u,v)w(x,y)w(u, v) \leq w(x, y). Assim sendo, se a MST contém w(x,y)w(x, y), podemos sem dúvidas afirmar que w(u,v)=w(x,y)w(u, v) = w(x, y), e que tanto TT como SS serão MSTs (diferentes).

Abaixo podemos ver uma imagem que exemplifica o ciclo criado por pp e (u,v)(u, v) referido acima, bem como o facto de tanto (u,v)(u, v) como (x,y)(x, y) cruzarem o corte.

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

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

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

O ciclo while é percorrido Θ(V)\Theta(V) vezes, com operação extractMin a levar O(logV)O(\log V) tempo. Todas as arestas são percorridas durante o decorrer do algoritmo O(E)O(E), e a operação implícita de atualização da queue leva O(logV)O(\log V) tempo. Assim sendo, podemos afirmar que, no total, a complexidade temporal do algoritmo é O((V+E)logV)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, SS, inicialmente com V|V| árvores (uma por vértice). Cada árvore corresponde a um conjunto disjunto, um set, sem elementos repetidos. EE é inicialmente ordenado por ordem crescente de peso dos seus arcos e, seguindo essa mesma ordem, o algoritmo percorre todas as arestas de EE. A cada momento, é escolhida uma aresta (u,v)(u, v), e é verificado se atualmente uu e vv pertencem a árvores diferentes em SS - 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.

Exemplo da aplicação do algoritmo

Começamos com o grafo abaixo (note-se que já estamos no primeiro passo, em que foi escolhido o arco (h,g)(h, g), com menor peso). Como atualmente hh e gg não pertencem à mesma árvore, os respetivos sets são unidos, e (h,g)(h, g) é adicionado à MST.

De seguida, temos 2 arcos com peso 2 - podemos escolher qualquer um, o algoritmo escolhe (c,i)(c, i). Os vértices não pertencem à mesma árvore, pelo que as respetivas árvores são unidas, e (c,i)(c, i) é adicionado à MST.

Escolhemos, agora, o outro arco com peso 2, (g,f)(g, f). gg e ff não pertencem à mesma árvore, pelo que as respetivas árvores ({g,h}\{g, h\} e {f}\{f\}) são unidas, com (g,f)(g, f) adicionado à MST.

O resto do algoritmo passa sempre por fazer a mesma coisa:

No passo abaixo, a aresta (h,i)(h, i) não é adicionada, já que hh e ii já pertencem à mesma árvore - qualquer aresta a ser adicionada formaria um ciclo.

No fim, o conjunto-resposta de arestas será:

A={(h,g),(i,c),(g,f),(a,b),(c,f),(c,d),(a,h),(d,e)}.A = \{(h, g), (i, c), (g, f), (a, b), (c, f), (c, d), (a, h), (d, e)\}.

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(ElogV)O(E \log V). Dissecando-o em pormenor, temos que:

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

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

São realizadas O(E)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α(V))O(E \cdot\alpha(V)), onde α(V)\alpha(V) é uma função de crescimento prolongado (sub-logarítmico). Visto que E<V2E < V^2, temos necessariamente que logE=O(logV)\log E = O(\log V), e que o algoritmo tem complexidade temporal O(ElogV)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 LCAsLCAs (lowest common ancestors).

Prova da Correção do Algoritmo

Podemos provar por indução que, se SS é um conjunto de arestas escolhido pelo algoritmo a qualquer momento do mesmo, então há pelo menos uma MST TT tal que STS \subseteq T.

Começando pelo caso base, S={}S = \{ \}, temos que STS \subseteq T, já que o conjunto vazio está contido em qualquer conjunto.

Podemos, então, partir para o caso geral - tenhamos então que estamos a explorar uma dada aresta ee, e que, segundo Kruskal, queremos adicioná-la:

  • Caso ee forme um ciclo com TT, a aresta não seria escolhida pelo algoritmo, pelo que a afirmação inicial mantém-se.

  • Caso TT contenha ee, a afirmação inicial mantém-se (é correto que o algoritmo a escolha).

  • Caso TT não contenha ee, T+eT + e contém necessariamente um ciclo (qualquer arco adicionado a uma MST gera um ciclo). O ciclo terá, necessariamente, de conter uma outra aresta, ff, aresta essa que não está em SS. Tal como na prova do algoritmo de Prim, o objetivo aqui passará por remover ff a TT e adicionar-lhe ee, ficando assim com outra árvore abrangente, TT'. Ora, se o peso de ff fosse menor que o de ee, ff já teria sido selecionada por Kruskal, pelo que w(e)w(f)w(e) \leq w(f). Assim sendo, w(T)w(T)w(T') \leq w(T). Como partimos de TT ser uma MST, então só podemos ter w(T)=w(T)w(T) = w(T'), e portanto a adição de ee por Kruskal levará também a uma MST. A afirmação inicial mantém-se.

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α(n))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, SS, 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 SS.

  • 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 SS.

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 - SS é, 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 SS; à 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 - nn chamadas a union podem levar à criação de uma árvore linear de nn nós em cadeia, algo que não queremos (a operação findSet levaria até nn subidas pela árvore, por exemplo). Podemos, claro, melhorá-la, e vamos fazê-lo seguindo um par de heurísticas:

União por Categoria

O representante de cada árvore mantém um majorante para o tamanho da árvore em que se encontra, o rank. Aquando da união de duas árvores, a raiz da árvore mais pequena passa a apontar para a raiz da maior, levando assim a uma complexidade temporal O(logn)O(\log n) para findSet:

Temos, claro, que aquando de makeSet o rank é inicializado a zero, e que a cada união o rank da árvore maior pode ser aumentado (caso aumente com a introdução da nova sub-árvore). Já que findSet corresponde a, na pior das hipóteses, subir a árvore toda a partir de uma das folhas até a raiz, a sua complexidade é agora O(logn)O(\log n), com esta alteração.

Compressão de Caminhos

Cada operação findSet achata a árvore de procura que está a explorar, colocando cada nó a apontar diretamente para o representante do conjunto.

Podemos na imagem acima observar o antes e depois do efeito que a operação findSet(a) tem na árvore - todas as procuras seguintes serão efetivamente realizadas em tempo constante.

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 mm operações levará, então, O(mα(n))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 108010^{80}, podemos considerar α(n)4\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(mlogn)O(m \cdot \log n), já assim bastante melhor que a original O(mn)O(mn).

Exemplo da aplicação de Union sucessivamente

Tenhamos que inicialmente SS encontra-se assim:

Chamar sucessivamente union(A, B), union(B, C), union(D, E) e union(F, G) produzirá os seguintes resultados:

De seguida, é chamado union(D, F). Para achatar a árvore, temos de chamar de novo findSet com um dos nós para ver o efeito a ser produzido (numa possível chamada futura de union um efeito semelhante seria observado).

Finalizamos ao unir as duas árvores finais, e a observar o achatamento (não completo) da árvore resultante com uma chamada findSet: