Algorithm a Kruskal - o le fausia o se fuafuaga e silisili ona lelei

I le geometer senituri lona 19 vave faatulaga Jakob Steiner mai Berlin le galuega o le auala e fesootai nuu e tolu ina ia latou le umi o le puupuu. Mulimuli ane, sa ia aoteleina le faafitauli: e manaomia e maua ai se nofoaga i totonu o se vaalele, o le mamao ese ai i n isi vaega na sili ona maualalo. I le senituri lona 20, o loo faaauau pea ona galulue i lenei autu. Sa filifili e faaalu ni nai manatu ma fesootai i latou i se auala e le mamao i le va oi latou o le puupuu. O uma se tulaga faapitoa o le faafitauli o loo suesueina.

"Matapeʻapeʻa" algorithm

algorithm a Kruskal e faatatau i le "matapeʻapeʻa" algorithm (e taʻua foi gradient). O le ute o latou - o le malo sili ona maualuga i laasaga taitasi. Le o taimi uma, "matapeʻapeʻa" algorithms tuuina atu le tali e sili ona lelei i le faafitauli. O loo i ai se manatu, e faaalia ai ia latou talosaga i galuega faapitoa e tuuina atu i le fofo optimum. o le talitonuga lenei o matroids. algorithm a Kruskal e faatatau i ia faafitauli.

Mauaina o se mamafa tino maualalo

Manatu algorithm fausia se faitauga faavaa e silisili ona lelei. O le faafitauli o le ai e faapea. Dan undirected kalafi aunoa tutusa pito ma loops, ma le seti o pito ua tuuina atu le galuega tauave mamafa w, lea e tofia e le numera e pito taitasi - ivi asoaso mamafa - w (e). O le mamafa o taitasi subset o ai le faia o ribs o le aofaiga o le mamafa o lona pito. Manaomia e maua ai le auivi o se mamafa laiti.

faʻamatalaga

algorithm a Kruskal galue. Muamua, pito uma o le kalafa muamua o loo faatulagaina i aʻe faatulagaga o le mamafa. Le taimi muamua, o le tino e le aofia ai so o ribs ae aofia vertices uma. Ina ua mavae le laasaga e sosoo ai o le algorithm i le vaega ua uma ona fausia o le tino mate, o se vaomatua spanning, o se tasi pito ua faaopoopo. E le filifilia le faafuaseʻi. Uma le pito o le kalafi, e le auai i le faavaa, e mafai ona taʻua o mumu ma lanumeamata. O le pito i luga o le tasi pito mumu ua i ai i le vaega lava lea e tasi o loo fausiaina connectivity vaomatua, ma le tumutumu green - eseese. O le mea lea, afai e te faaopoopo i ai i le mata mumu, o loo i ai i le taamilosaga, ma pe afai o le green - e pei ona maua i lenei laasaga o fafie fesootai vaega o le a itiiti ifo i lo le tasi. O lea, o le taunuuga o le fausiaina e le mafai ona faaopoopo se pito mumu, ae e mafai ona faaopoopo i ai se pito green e maua i le vaomatua. Ma faaopoopo mai se pito lanu meamata ma le mamafa aupito i maualalo. Le taunuuga o se faavae o le mamafa aupito i maualalo.

faatinoga

Faailoaina o le vaomatua i le taimi nei F. E vaevaeina le seti o vertices i le fanua o connectivity (latou faatasiga ituaiga F, ma ua latou disjoint). I uma pito o le vertices mumu latou i ai i se vaega e tasi. Vaega (x) - o le galuega tauave o le tasi i vertex x toe foi se vaega o le igoa, ei x. Tuufaatasia (x, y) - o se taualumaga e fausia se vasega fou, e aofia ai le tuufaatasia o vaega o x ma y ma le isi vaega uma. Ia n - numera o pito. o loo aofia uma nei manatu faavae i algorithm a Kruskal. faatinoga:

1. Faatulaga pito uma o le kalafi mai le 1 i n-th mamafa aʻe. (Ai, tietie i - i i luga le numera pito).

2. mo i = 1 i le n faia.

3. x: = Vaega (ai).

4. y: = Vaega (laitiiti).

5. Afai x e le y tutusa aufaatasi lea (x, y), e aofia ai ma le i F pito numera.

saʻo

Ia T - faavaa o le kalafi uluai fausia le faaaogaina o le algorithm Kruskal ma S - ona tulaga soʻona faia. Ua ia i tatou e faamaonia ai w (T) e le sili atu nai lo w (S).

Ia M - plurality o fins S, P - a plurality o fins T. Afai e le tutusa S e T, ona leai lea o se 'ua ivi asoaso faavaa T, e le auai i S. S. iā adjoin le faataamilosaga, ua valaauina C. F aveese mai so o se pito es, auai S. tatou te maua se faavaa fou, aua e tutusa lava le pito ma vertices. e le sili atu lona mamafa nai lo w (S), talu w (iā) e leai se toe w (es) i se mana algorithm Kruskal. Lenei taotoga (suia ribs T S i ribs) o le a toe faia i le umi e maua T. O le mamafa o mulimuli ane e le sili faavaa maua taitasi nai lo le mamafa talu ai, o lona uiga e w (T) e le sili atu nai lo w (S).

O le robustness o algorithm a Kruskal faapea mai le theorem o Rado-Edmonds i matroids.

Talosaga Faataitaiga algorithm Kruskal

kalafi Dan ma nodes a, b, c, d, e ma ribs (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). o loo faaalia ai le mamafa o le pito i totonu o le laulau ma le fuainumera. Le taimi muamua, fausia vaomatua F loo vertices uma o le kalafi ma e le aofia ai so o ribs. Algorithm Kruskal muamua faaopoopo ivi asoaso (a, e), talu mai le mamafa sa i ai le pito i lalo, ma le vertices a ma e ua connectivity laau i vaega eseese F (ivi asoaso (a, e) o le lanu meamata), lea o le ivi asoaso (c, d), ona e le itiiti ifo lenei mamafa faatausiusiuga o pito kalafi, e le auai i F, ma e lanu meamata, lea mo le mafuaaga lava lea e tasi faatupulaia tafatafa (a, b). Ae o le pito (b, e) ua mavae, e ui lava o ia ma le mamafa aupito i maualalo o le pito o totoe, ona ua mumu: o le vertices b ma e auai i le vaega lava lea e tasi o le vaomatua connectivity F, o lona uiga, pe afai tatou te faaopoopo atu F le pito (b, e), ua faia e taamilosaga. Ona faaopoopo pito lanu meamata (b, c), e mavae pito mumu (c, e), ona d, e. O lea, e faaopoopo pito faasolosolo (a, e), (c, d), (a, b), (b, c). Mai nihera silisili ona lelei mo tino ma e aofia ai le kalafa muamua. O lea la i le tulaga lenei faagaoioia se algorithm Kruskal. o loo faaalia se faataitaiga.

Le fuainumera faaalia ai se kalafi, lea e aofia ai vaega fesootai e lua. O laina lototele faailoa le ribs faavaa e silisili ona lelei (lanu meamata) fausia le faaaogaina o le algorithm Kruskal.

O le ata o tumutumu e faaalia ai le kalafa muamua, ma le pito i lalo - o se auivi o mamafa itiiti, na fausia ai ia te ia e ala i le faaaogaina o le algorithm.

O le faasologa o le ribs faaopoopo (1.6); (0,3), (2,6) po o (2,6), (0,3) - e le taua; (3,4); (0,1), (1,6) po o (1,6), (0,1), tausia foi (5,6).

algorithm a Kruskal maua talosaga talafeagai, mo se faataitaiga, e optimize le fesootaiga gasket, auala i fou esetete fale nofoaga i atunuu taitasi, faapea foi i isi mataupu.