Esercizio 5.2.7

0 passi visti su 3

Consegna

Dato il grafo non orientato G=(V,E)G = (V, E) con 11 nodi e archi [1,2][1,2] 1, [1,4][1,4] 5, [1,6][1,6] 3, [1,7][1,7] 1, [2,3][2,3] 5, [2,4][2,4] 3, [2,5][2,5] 2, [2,6][2,6] 4, [3,5][3,5] 9, [3,6][3,6] 4, [3,9][3,9] 1, [4,5][4,5] 3, [5,7][5,7] 2, [5,10][5,10] 4, [6,8][6,8] 6, [6,9][6,9] 2, [8,11][8,11] 4, [9,10][9,10] 1, [10,11][10,11] 5:

  1. se ne determini l'albero di copertura di costo totale minimo ed il relativo costo applicando l'algoritmo di Kruskal;
  2. si indichi giustificandola la complessità dell'algoritmo di Kruskal.
Apri in Kruskal
0Kruskalapri

Archi presi, nell'ordine: [1,2][1,2] 1, [1,7][1,7] 1, [3,9][3,9] 1, [9,10][9,10] 1, [2,5][2,5] 2, [6,9][6,9] 2, [1,6][1,6] 3, [2,4][2,4] 3, [8,11][8,11] 4, [10,11][10,11] 5. Si scartano [5,7][5,7], [4,5][4,5], [2,6][2,6], [3,6][3,6], [5,10][5,10], [1,4][1,4] e [2,3][2,3], che chiuderebbero un ciclo. Con il decimo arco preso, n−1=10n - 1 = 10, ci si ferma.

1Soluzioneapri

L'albero costa 1+1+1+1+2+2+3+3+4+5=231 + 1 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 5 = 23.

2Complessitàapri

O(mlog⁡n+n2)O(m \log n + n^2). Ordinare gli mm archi costa O(mlog⁡m)=O(mlog⁡n)O(m \log m) = O(m \log n), perché m<n2m < n^2; il confronto fra C[i]C[i] e C[j]C[j] costa O(1)O(1) e si fa al più mm volte; ogni unione scorre il vettore CC, O(n)O(n), e le unioni sono al più n−1n - 1.