Albero coprente a costo minimo - Algoritmo di Kruskal
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Elenco degli archi in ordine di peso crescente
Arco Peso Usato B - D 1 C - F 3 F - G 4 A - E 5 C - G 5 A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Considero l'arco B-D
Archi
Arco Peso Usato B - D 1 C - F 3 F - G 4 A - E 5 C - G 5 A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 0 A 1 B 2 C 3 D 4 E 5 F 6 G
Includo l'arco B-D perchè i due nodi non appartengono allo stesso gruppo (gruppo 1 - gruppo 3)
B-D (gruppo 1 - gruppo 3) SI
Unione del gruppo 1 e del gruppo 3
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco C-F
Archi
Arco Peso Usato B - D 1 SI C - F 3 F - G 4 A - E 5 C - G 5 A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 0 A 2 C 3 B D 4 E 5 F 6 G
Includo l'arco C-F perchè i due nodi non appartengono allo stesso gruppo (gruppo 2 - gruppo 5)
C-F (gruppo 2 - gruppo 5) SI
Unione del gruppo 2 e del gruppo 5
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco F-G
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 A - E 5 C - G 5 A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 0 A 3 B D 4 E 5 C F 6 G
Includo l'arco F-G perchè i due nodi non appartengono allo stesso gruppo (gruppo 5 - gruppo 6)
F-G (gruppo 5 - gruppo 6) SI
Unione del gruppo 5 e del gruppo 6
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco A-E
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 C - G 5 A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 0 A 3 B D 4 E 6 C F G
Includo l'arco A-E perchè i due nodi non appartengono allo stesso gruppo (gruppo 0 - gruppo 4)
A-E (gruppo 0 - gruppo 4) SI
Unione del gruppo 0 e del gruppo 4
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco C-G
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 3 B D 4 A E 6 C F G
Non posso includere l'arco C-G perchè i due nodi appartengono allo stesso gruppo (gruppo 6)
C-G (gruppo 6) NO
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco A-D
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 3 B D 4 A E 6 C F G
Includo l'arco A-D perchè i due nodi non appartengono allo stesso gruppo (gruppo 4 - gruppo 3)
A-D (gruppo 4 - gruppo 3) SI
Unione del gruppo 4 e del gruppo 3
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco A-B
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 SI A - B 7 E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 3 A B D E 6 C F G
Non posso includere l'arco A-B perchè i due nodi appartengono allo stesso gruppo (gruppo 3)
A-B (gruppo 3) NO
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco E-G
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 SI A - B 7 -- E - G 8 A - G 9 A - C 10 B - E 11
Gruppi
Gruppo Nodi 3 A B D E 6 C F G
Includo l'arco E-G perchè i due nodi non appartengono allo stesso gruppo (gruppo 3 - gruppo 6)
E-G (gruppo 3 - gruppo 6) SI
Unione del gruppo 3 e del gruppo 6
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco A-G
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 SI A - B 7 -- E - G 8 SI A - G 9 A - C 10 B - E 11
Gruppi
Non posso includere l'arco A-G perchè i due nodi appartengono allo stesso gruppo (gruppo 6)
A-G (gruppo 6) NO
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco A-C
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 SI A - B 7 -- E - G 8 SI A - G 9 -- A - C 10 B - E 11
Gruppi
Non posso includere l'arco A-C perchè i due nodi appartengono allo stesso gruppo (gruppo 6)
A-C (gruppo 6) NO
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Considero l'arco B-E
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 SI A - B 7 -- E - G 8 SI A - G 9 -- A - C 10 -- B - E 11
Gruppi
Non posso includere l'arco B-E perchè i due nodi appartengono allo stesso gruppo (gruppo 6)
B-E (gruppo 6) NO
grafo
A
A
B
B
A--B
7
C
C
A--C
10
D
D
A--D
6
E
E
A--E
5
G
G
A--G
9
B--D
1
B--E
11
C--G
5
F
F
C--F
3
E--G
8
F--G
4
Copertura del grafo
grafo
A
A
B
B
A--B
C
C
A--C
D
D
A--D
6
E
E
A--E
5
G
G
A--G
B--D
1
B--E
C--G
F
F
C--F
3
E--G
8
F--G
4
Archi
Arco Peso Usato B - D 1 SI C - F 3 SI F - G 4 SI A - E 5 SI C - G 5 -- A - D 6 SI A - B 7 -- E - G 8 SI A - G 9 -- A - C 10 -- B - E 11 --
Gruppi
