Albero coprente a costo minimo - Algoritmo di Kruskal

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

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

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

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

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

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

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

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

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

Gruppo	Nodi
6	A B C D E F G

Non posso includere l'arco A-G perchè i due nodi appartengono allo stesso gruppo (gruppo 6)

A-G (gruppo 6) NO

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

Gruppo	Nodi
6	A B C D E F G

Non posso includere l'arco A-C perchè i due nodi appartengono allo stesso gruppo (gruppo 6)

A-C (gruppo 6) NO

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

Gruppo	Nodi
6	A B C D E F G

Non posso includere l'arco B-E perchè i due nodi appartengono allo stesso gruppo (gruppo 6)

B-E (gruppo 6) NO

Copertura del grafo

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

Gruppo	Nodi
6	A B C D E F G