DAA - Spanning Tree

UMA spanning tree é um subconjunto de um gráfico não direcionado que possui todos os vértices conectados por um número mínimo de arestas.

Se todos os vértices estiverem conectados em um gráfico, então existe pelo menos uma árvore estendida. Em um gráfico, pode haver mais de uma árvore de abrangência.

Propriedades

• Uma árvore geradora não tem nenhum ciclo.
• Qualquer vértice pode ser alcançado a partir de qualquer outro vértice.

Exemplo

No gráfico a seguir, as arestas destacadas formam uma árvore geradora.

Árvore de alcance mínimo

UMA Minimum Spanning Tree (MST)é um subconjunto de arestas de um gráfico não direcionado ponderado conectado que conecta todos os vértices junto com o peso de aresta total mínimo possível. Para derivar um MST, o algoritmo de Prim ou o algoritmo de Kruskal podem ser usados. Portanto, discutiremos o algoritmo de Prim neste capítulo.

Conforme discutimos, um gráfico pode ter mais de uma árvore de abrangência. Se houvern número de vértices, a árvore de abrangência deve ter n - 1número de arestas. Nesse contexto, se cada aresta do gráfico estiver associada a um peso e houver mais de uma árvore geradora, precisamos encontrar a árvore geradora mínima do gráfico.

Além disso, se houver quaisquer arestas ponderadas duplicadas, o gráfico pode ter múltiplas árvores geradoras mínimas.

No gráfico acima, mostramos uma árvore de abrangência, embora não seja a árvore de abrangência mínima. O custo desta árvore abrangente é (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Usaremos o algoritmo de Prim para encontrar a árvore geradora mínima.

Algoritmo de Prim

O algoritmo de Prim é uma abordagem gananciosa para encontrar a árvore geradora mínima. Neste algoritmo, para formar um MST, podemos partir de um vértice arbitrário.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

A função Extract-Min retorna o vértice com custo mínimo de aresta. Esta função funciona em min-heap.

Exemplo

Usando o algoritmo de Prim, podemos começar de qualquer vértice, vamos começar do vértice 1.

Vértice 3 está conectado ao vértice 1 com custo mínimo de borda, portanto, borda (1, 2) é adicionado à árvore de abrangência.

Próximo, borda (2, 3) é considerado porque este é o mínimo entre as arestas {(1, 2), (2, 3), (3, 4), (3, 7)}.

Na próxima etapa, obtemos vantagem (3, 4) e (2, 4)com custo mínimo. Beira(3, 4) é selecionado aleatoriamente.

De maneira semelhante, as bordas (4, 5), (5, 7), (7, 8), (6, 8) e (6, 9)são selecionados. Como todos os vértices são visitados, agora o algoritmo para.

O custo da árvore geradora é (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. Não há mais árvore geradora neste gráfico com custo menor que 23.