Algoritme de Kruskal
L'algoritme de Kruskal és un algoritme de la teoria de grafos per a trobar un arbre recubridor mínim en un grafo conexo i ponderat. És dir, busca un subconjunt d'arestes que, formant un arbre, inclouen tots els vèrtiços i a on el valor de la suma de totes les arestes de l'arbre és el mínim. Si el grafo no és conexo, llavors busca un bosc expandit mínim (un arbre expandit mínim per a cada component conexa). Este algoritme pren el seu nom de Joseph Kruskal, qui ho va publicar per primera volta en 1956.[1] [2] . Atres algoritmes que servixen per a trobar el arbre d'expansió mínima o arbre recubridor mínim són l'algoritme de Prim, l'algoritme del borrador invers i l'algoritme de Boruvka.
Descripció
L'algoritme de Kruskal és un eixemple d'algoritme voraç que funciona de la següent manera:
- es crea un bosc B (un conjunt d'arbres), a on cada vèrtiç del grafo és un arbre separat
- es crea un conjunt C que continga a totes les arestes del grafo
- mentres C és no buide
- eliminar una aresta de pes mínim de C
- si eixa aresta conecta dos arbres diferents s'afig al bosc, combinant els dos arbres en un sol arbre
- en cas contrari, es rebuja l'aresta
En acabar l'algoritme, el bosc té un sol component, el qual forma un arbre d'expansió mínim del grafo.
En un arbre d'expansió mínim es complix:
- la cantitat d'arestes de l'arbre és la cantitat de nodos menys un (1).
Pseudocódigo
funció Kruskal(G)
Per a cada v en V[G] fer
Nou conjunt C(v) ← {v}.
Nou heap Q que conté totes les arestes de G, ordenant pel seu pes
Definixc un arbre T ← Ø
// n és el número total de vèrtiços
Mentres T tinga menys de n-1 arestes i !Q.buit() fer
(o,v) ← Q.sacarMin()
// prevé cicles en T. agrega (o,v) si o i v estan
// diferents components en el conjunt.
// Note's que C(o) torna la component a la que pertany o
Si C(v) ≠ C(o) fer
Agregar aresta (v,o) a
T Merge C(v) i C(o) en el conjunt
Respondre arbre T
Referències
- ↑ (1956).«On the shortest spanning subtree and the traveling salesman problem».Proceedings of the American Mathematical Society.(7)
- 48-50.doi:10.1090/S0002-9939-1956-0078686-7.
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Secció 23.2: The algorithms of Kruskal and Prim, pp.567–574.
Referències
- Este artícul conté una traducció derivada de «Algoritmo de Kruskal» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.