( 9 pontos) Determine a árvore geradora mínima do grafo ponderado representado pela matriz de adjacências abaixo, usando o algoritmo de Prim iniciando-se do vértice 1. A cada passo (adição de um novo vértice à árvore), mostre como fica o array pai, como ilustrado abaixo. Considere a indexação a partir do zero, como na linguagem C (índices dos vértices de 0 a 3 ).
Considerações: i) No passo 1 abaixo, o vértice 1 tem como pai a si próprio por ser o vértice inicial - “raiz” - da AGM; ii) os vértices com pai =-1 são os que ainda não foram acrescentados à AGM.
\left[\begin{array}{cccc} 0 & 15 & 10 & 19 \\\\ 15 & 0 & 0 & 7 \\\\ 10 & 0 & 0 & 16 \\\\ 19 & 7 & 16 & 0 \end{array}\right]

Resposta:

Passo 1: Pai : |-1| 1|-1|-1 \mid

Passo 1

O enunciado pede a árvore geradora mínima de um grafo de 4 vértices, com matriz de adjacência
\begin{pmatrix} 0 & 15 & 10 & 19\\\\ 15 & 0 & 0 & 7 \\\\ 10 & 0 & 0 & 16\\\\ 19 & 7 & 16 & 0 \end{pmatrix}
usando o algoritmo de Prim iniciado em 1 (indexação de 0 a 3).
Vamos manter
– um array \,key[\,] com o menor peso de aresta que liga cada vértice ao conjunto já construído,
– um array \,parent[\,] que aponta, para cada vértice, seu pai na árvore.
Inicialização: para todo i\neq1, key[i]=\infty e parent[i]=-1; e
key[1]=0,\quad parent[1]=1.
Ao incluir o vértice inicial 1, o array pai fica:
parent = [-1,\;1,\;-1,\;-1].

Passo 2

Examinamos as arestas saindo de 1:
(1,0)=15 e (1,3)=7.
Atualizamos
key[0]=15,\;parent[0]=1, \quad key[3]=7,\;parent[3]=1, \quad key[2]=\infty.
O menor key entre não incluídos é key[3]=7. Incluímos o vértice 3, atualizando
parent = [-1,\;1,\;-1,\;1].

Passo 3

Agora olhamos as arestas de 3:
(3,2)=16 key[2] passa a 16 e parent[2]=3.
(3,0)=19 não melhora key[0]=15.
Os não incluídos têm key[0]=15 e key[2]=16; escolhe-se 0. Ao incluir 0, temos
parent = [-1,\;1,\;3,\;1].

Passo 4

Finalmente, a partir de 0:
(0,2)=10 melhora key[2] para 10 e define parent[2]=0.
Só resta 2 com key[2]=10, que é incluído, resultando em
parent = [1,\;1,\;0,\;1].

Resposta

A AGM obtida contém as arestas
(1,3)\;(\text{peso }7),\quad (1,0)\;(\text{peso }15),\quad (0,2)\;(\text{peso }10)
e peso total 7+15+10=32.
O array final de pais é
[1,\;1,\;0,\;1].

Exercícios relacionados