Algorisme de Kruskal: diferència entre les revisions

En [[teoria de grafs]], l''''algorisme de Kruskal''' és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf.<ref name=":0">{{Cite bookref-llibre|title títol= Introduction To Algorithms|last cognom= Cormen|first nom= Thomas|publisher editorial= MIT Press|year any= 2009|isbn = 0262258102|location lloc= |pages pàgines= 631|last2 cognom2= Charles E Leiserson, Ronald L Rivest, Clifford Stein|edition edició= Third}}</ref> Es tracta d'un [[algorisme voraç]] ja que troba l'arbre generador mínim per un [[Glossari de teoria de grafs#G#Graf ponderat|graf ponderat]] connex afegint arcs de pes superior en cada pas.<ref name=":0" /> Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un ''bosc generador mínim'' (un arbre generador mínim per a cada component connex).

Aquest algorisme va aparèixer per primer cop a ''Proceedings of the American Mathematical Society'', pp. 48–50 el 1956 i va ser escrit per Joseph Kruskal.<ref>{{Cite journal ref-publicació| last1 cognom1= Kruskal | first1 nom1= J. B. | authorlink1 = Joseph Kruskal| doi = 10.1090/S0002-9939-1956-0078686-7 | title títol= On the shortest spanning subtree of a graph and the traveling salesman problem | journal publicació= [[Proceedings of the American Mathematical Society]] | volume volum= 7 | pages pàgines= 48–50 | year any= 1956| jstor = 2033241| pmid = | pmc = }}</ref>