Kruskalen algoritmo
(«Kruskalen algoritmoa» orritik birbideratua)
Kruskal-en algoritmoa grafoen teoriako algoritmo bat da; grafo konexu eta pisudun batean zuhaitz estaltzaile minimo bat aurkitzeko. Hau da, ertzen azpi-multzo bat bilatzen du, zuhaitz bat osatuz, non grafoko erpin guztiak sartzen diren eta zuhaitzeko ertzen guztien baturaren balioa minimoa den. Grafua konexua ez bada, baso hedatzaile minimo bat bilatzen du.
Algoritmo hau Joseph Kruskalen izena du, lehenengoz 1956an argitaratu zuelako. Kruskalena bezalako beste algoritmo batzuk dira Primen algoritmoa, borratzaile alderantzizko algoritmoa eta Boruvkaren algoritmoa.
Kanpo estekak
[aldatu | aldatu iturburu kodea]| Autoritate kontrola |
|
|---|
Datuak: Q797860
Multimedia: Kruskal's algorithm / Q797860
|
Artikulu hau matematikari buruzko zirriborroa da. Wikipedia lagun dezakezu edukia osatuz. |