Barion Pixel Minimális feszítőfa és a Kruskal-algoritmus | mateking
 

Számítástudomány epizód tartalma:

Itt röviden és szuper-érthetően elmeséljük, hogyan lehet egy gráfban megtalálni a minimális feszítőfát. Egy súlyozott gráfban a Kruskal-algoritmus segítségével találjuk meg a minimális élsúlyokkal rendelkező feszítőfát.

A képsor tartalma

Ez a vasúti hálózat egy gráf.

Megmutatja, hogy mely állomások között vezetnek vasútvonalak.

Ha ellátjuk az éleket súlyokkal…

Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.

Vagy hány percig tart a két állomás közötti út.

Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.

Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…

akkor a gráfnak egy feszítőfáját kapjuk.

Feszítőfából általában több is van.

És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…

Van itt ez a gráf, és rendeljünk hozzá az éleihez nem negatív valós számokat.

Ezeket a számokat súlyoknak nevezzük.

Képzeljük el, hogy ez a gráf egy úthálózat, vagy mondjuk egy elektromos hálózat, az élek súlyai pedig az áthaladás költsége.

Készítsük el ebben a gráfban a minimális súlyú feszítőfát.

Ez egy olyan hálózat lesz, amin keresztül bármely csúcsból bármely csúcsba el lehet jutni, de a benne szereplő élek súlyainak összege minimális.

Vagyis ez a legolcsóbban működtethető olyan hálózat, ami az összes csúcsot tartalmazza.

A minimális feszítőfát a Kruskal algoritmus segítségével lehet megtalálni.

Maga az algoritmus nagyon egyszerű.

Az első lépés, hogy keressük meg a gráfban a legkisebb súlyú élt.

Ha több azonos súlyú él van, akkor válasszuk ki azt, amelyikhez kedvünk van.

Ezek után belépünk egy ciklusba, ahol minden lépésben az eddig még ki nem választott élekre alkalmazzuk az előző lépést úgy, hogy ne keletkezzen kör.

Ha mégis kör keletkezik, akkor a legutolsó olyan élt, amelynek hozzávétele során a kört kapjuk, töröljük.

Most éppen van még egy 1-es él…

sőt még egy.

Aztán jönnek a 2-es élek.

Hopp, itt keletkezett egy kör.

Az nem jó, akkor ezt a legutóbbi élt töröljük.

A 2-esekbből kifogytunk, jönnek a 3-asok.

Elfogytak a 3-asok is, úgyhogy jöhetnek a 4-esek.

Ajaj, úgy tűnik mégse…

Hát akkor jöhet az 5-ös.

Aztán a 6-os.

Abból úgy tűnik csak ez az egy van.

Aztán itt jönnek a 7-esek.

A 8-asok…

Végül a 9-esek.

És voila, itt a minimális súlyú feszítőfa.

Az algoritmus röviden így írható le:

Legkisebb súlyú él kiválasztása

Kör keletkezik:

az élt töröljük

Nem keletkezik kör:

az élt megtartjuk

Vesszük a megmaradó

ki nem választott éleket

Egy gráfban lehet több minimális feszítőfa is.

Ez most is így van..

 

Minimális feszítőfa és a Kruskal-algoritmus

01
hang
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez