( 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.
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
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