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">{{ref-llibre|títol= Introduction To Algorithms|cognom= Cormen|nom= Thomas|editorial= MIT Press|any= 2009|isbn = 0262258102|lloc= |pàgines= 631|cognom2= Charles E Leiserson, Ronald L Rivest, Clifford Stein|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).