Borůvkan algoritmi
Borůvkan algoritmi_Anim.gif)
Borůvkan algoritmia edustava animaatio versiossa ilman supistumista.
| Löytäjä tai keksijä | Otakar Borůvka |
|---|---|
| Julkaisupäivämäärä | 1926 |
| Liittyvät ongelmat | Graafiteorian algoritmi ( d ) , matemaattinen käsite ( d ) |
Borůvka algoritmi on haku algoritmi varten virittävä puu vähäinen paino on painotettu kaavio . Sitä kutsutaan myös Sollinin algoritmiksi .
Pienin kattava puuongelma
In graafiteoria , annetaan liitetty suuntaamattoman graafin , jonka reunat on painotettu, virittävän puun vähäinen paino tämä kuvaaja on virittävä puu ( osajoukko , joka on puu , ja joka yhdistää kaikki kärkipisteet yhdessä), joiden summa on reunan painot on minimaalinen.
Algoritmi
Periaate
Periaatteena on vähentää G: tä supistamalla reunoja : valitsemme asteittain puussa olevat reunat, ja joka kerta kun valitsemme yhden, yhdistämme solmut, jotka tämä reuna yhdistää. Joten lopussa on vain yksi kärki.
Voimme myös kuvata algoritmin puhumatta supistumisesta: rakennamme metsän, jonka puut sulautuvat vähitellen muodostaen vähimmäispainon kattavan puun.
Pseudokoodi
Otetaan graafi G ja F valittujen reunojen joukko (täytämme sen vähitellen).
1 F ← vide 2 Tant que G n'est pas réduit à un sommet faire 3 Détruire les boucles de G (*) 4 Remplacer les arêtes multiples entre deux sommets par une seule dont le poids est le minimum 5 Pour tout x, sommet de G, faire 6 Trouver l'arête e_x de poids minimum adjacente à x 7 F ← F union e_x 8 Contracter e_x (**) 9 fin pour 10 fin tant que 11 renvoyer F;;(*) eli reunat, jotka alkavat ja saapuvat samaan kärkeen; tällainen reuna voi ilmestyä iteraation jälkeen.
(**) eli sulauta pisteet pisteissä
Monimutkaisuus
Borůvka algoritmi on monimutkaisuus on , jossa on reunojen lukumäärän ja pisteiden lukumäärä on pitää kuvaajan.
Vertailu muihin algoritmeihin
Pienimmän ulottuvan puun ongelmaan on muitakin algoritmeja, esimerkiksi Prim-algoritmi ja Kruskal-algoritmi .
Historiallinen
Borůvkan algoritmi on ensimmäinen Otakar Borůvkan vuonna 1926 julkaisema minimaalisen painon kattava puuhakualgoritmi , joka julkaistiin artikkelissa O jistém Problému minimálním ('' Tietystä vähimmäisongelmasta ''). Alun perin tarkoituksena oli tehdä sähköverkkoon ja Määrin tehokkaita. Se löydettiin uudelleen monta kertaa sen jälkeen.
Huomautuksia ja viitteitä
- Ivan Lavallée, " Tehokas rinnakkainen algoritmi pienimmän puun rakentamiseksi kaavioon ", RAIRO-Operations Research , voi. 19, n o 1, 1985, s. 57-69
- Graham-Hell, Pienin ulottuva puu -ongelman historiasta s. 52.
- ( Borůvka 1926 )
- Graham-Hell, Minimaalisen pintaongelman historiasta s. 47.
Bibliografia
- (cs) Otakar Borůvka , " O jistém Problému minimálním (Tietoja tietystä vähimmäisongelmasta) " , Práce mor. přírodověd. spol. v. Brně III , voi. 3,1926, s. 37–58
- (en) RL Graham ja Pavol Hell , ” Minimal Spanning Tree Problem History ” , Annals of the History of Computing , voi. 7, n o 1,Tammikuu 1985, s. 43–57 ( lue verkossa )
Ulkoinen linkki
- " Boruvka-algoritmi " , COATI, INRIA