o Valime graafist G vähima kaaluga serva k1 o Iga i=2, ..., n-1 korral valime graafist G sellise vähima kaaluga serva ki, mis erineb eelmistest ja ei moodusta nendega koos tsüklit Kruskali algoritmi korrektsus: o Algoritm töötab - 1 sammu, sest igal sammul leidub uus tingimusi rahuldav serv o Kruskali algoritmiga saadakse - 1 serva ja ülimalt tipuga graaf, mis ei sisalda tsükleid, järelikult ta on puu ja graafi toespuu o Olgu Kruskali algoritmiga saadud puu K servad 1, ..., -1. Tõestame, et selle puu kaal on toespuude seas vähim o Olgu 1 graafi suvaline toespuu o Vaatleme järgmist sammu: Olgu esimene Kruskali algoritmis valitud serv puus , mis ei kuulu puusse 1. o Kui lisame puule 1, siis tekib seal tsükkel, mis sisaldab serva . Mingi serv selles tsüklis ei kuulu puusse , sest puus pole tsükleid
• Algoritm: nagugi laiuti otsimine otsimisel tippe värvitakse kasutades kolme erinevat värvi: valge, hall, must. Lisaks iga tipuga seotakse kaks ajatemplit: märgitakse siis, kui tipp esimest korda avastati ja siis, kui tipp on lõplikult töödeldud ja mustaks värvitud 9.4.1 Näide kasutamisest: • Saab kasutada graafis tsüklite leidmiseks • Kahe tipu vahelise tee leidmiseks • Min toespuu leidmiseks 9.5 Laiuti otsimine • Kasutada ülesannete puhul, kus otsitakse parimat lahendust ja see tuleks välja sõeluda paljude võimaluste hulgast • Kõige tüüpilisemaks ülesandeks on leida lühimat teed kahe tipu vahel • Tippude vahele jäävaid kaarte arvu loetakse tee pikkuseks • Kõiki lahendusvariante uuritakse paralleelse, mitte ei võrrelda hiljem 9.5.1 Lahenduskäik • Võetakse lähtetipp
annaabi.ee 
