Bc. Vojtěch Hordějčuk

„Dejte mi pevný bod a já pohnu Zemí.” - Archimedes

Domů » Wiki » Grafové algoritmy » Algoritmus Jarník-Prim

Algoritmus Jarník-Prim

Jarníkův-Primův algoritmus je grafový algoritmus pro vyhledávání minimální kostry souvislého ohodnoceného grafu. Je pojmenovaný podle českého matematika Vojtěcha Jarníka (1897–1970) a amerického matematika Roberta Claye Prima (narozen 1921). Oba tento algoritmus popsali nezávisle na sobě, ale první byl Jarník (1930).

Kroky algoritmu

  • Vytvoř prázdný graf T.
  • Do grafu T vlož libovolný jeden uzel vstupního grafu G.
  • Dokud má graf T méně uzlů než vstupní graf G, opakuj:
    • Najdi hranu s minimálním ohodnocením, spojující graf T s rozdílem grafů G-T
    • Přidej tuto hranu do grafu T.

Příklad

Inicializace

Graf T, který Jarníkův-Primův algoritmus postupně generuje, je zpočátku prázdný. Modře jsou označeny hrany, které algoritmus v daném kroku ověřuje, zelený je graf T a žlutý naposledy přidaný uzel.

ukázkový graf

Krok 1

Náhodně je vybrán a do grafu T přidán uzel A. Bez prvního uzlu nemůže být algoritmus spuštěn. Na konkrétním uzlu skutečně nezáleží, protože budou nakonec v kostře zahrnuty všechny.

Graf T má menší počet uzlů než graf G, algoritmus tedy pokračuje.

prvním uzlem grafu T je uzel A

Krok 2

Nyní algoritmus vyhledá hranu s nejmenším ohodnocením, která graf T spojuje se zbývajícími uzly (rozdíl grafů G-T). Kandidáty jsou hrany (A-B), (A-F). Vybrána je hrana (A-F), protože má menší ohodnocení. Graf T má stále menší počet uzlů než graf G, algoritmus tedy pokračuje.

graf T již obsahuje uzly A, F

Krok 3

Dalšími kandidáty na rozšíření grafu T jsou hrany (F-E), (A-B). Vybrána je hrana (F-E), protože má menší ohodnocení. Graf T má stále menší počet uzlů než graf G, algoritmus tedy pokračuje.

graf T již obsahuje uzly A, F, E

Krok 4

Dalšími kandidáty na rozšíření grafu T jsou hrany (A-B), (E-B), (E-D). Vybrána je hrana (E-D), protože má menší ohodnocení. Graf T má stále menší počet uzlů než graf G, algoritmus tedy pokračuje.

graf T již obsahuje uzly A, F, E, D

Krok 5

Dalšími kandidáty na rozšíření grafu T jsou hrany (A-B), (E-B), (D-B), (D-G). Vybrána je hrana (D-B), protože má menší ohodnocení. Graf T má stále menší počet uzlů než graf G, algoritmus tedy pokračuje.

graf T již obsahuje uzly A, F, E, D, B

Krok 6

Dalšími kandidáty na rozšíření grafu T jsou hrany (B-C), (B-G), (D-G). Vybrána je hrana (B-C), protože má menší ohodnocení. Všimněte si, že hrany (A-B) a (E-B) uvažovány nejsou, protože nespojují graf T s rozdílem grafů G-T. Graf T má však stále menší počet uzlů než graf G, algoritmus tedy pokračuje.

graf T již obsahuje uzly A, F, E, D, B, C

Krok 7

Dalšími kandidáty na rozšíření grafu T jsou hrany (B-G), (D-G). Vybrána je hrana (B-G), protože má menší ohodnocení. Graf T má stejný počet uzlů jako graf G, výpočet může skončit.

graf T již obsahuje uzly A, F, E, D, B, C, G

Krok 8

Výpočet je dokončen. Graf T je minimální kostra grafu G.

zeleně je označená minimální kostra grafu G

Časová složitost

Jarníkův-Primův algoritmus lze naimplementovat s následující složitostí:

O(|E| + |V| \log (|V|))

Reference