Dlaczego algorytm Prima działa?
Dlaczego algorytm Prima działa?

Wideo: Dlaczego algorytm Prima działa?

Wideo: Dlaczego algorytm Prima działa?
Wideo: 3.5 Prims and Kruskals Algorithms - Greedy Method 2024, Marsz
Anonim

W informatyce Prima (znany również jako Jarník) algorytm jest chciwy algorytm który znajduje minimalne drzewo opinające dla ważonego grafu nieskierowanego. Oznacza to, że znajduje podzbiór krawędzi, który tworzy drzewo, które obejmuje każdy wierzchołek, gdzie całkowita waga wszystkich krawędzi w drzewie jest zminimalizowana.

Pod tym względem, dlaczego Prims jest lepszy od Kruskala?

Kruskala Algorytm: wykonuje lepszy w typowych sytuacjach (wykresy rzadkie), ponieważ wykorzystuje prostsze struktury danych. Prima Algorytm: jest znacznie szybszy w limicie, gdy masz naprawdę gęsty wykres z wieloma krawędziami niż wierzchołki.

czy algorytm Prima jest optymalny? Algorytm Prima jest chciwy algorytm za znalezienie minimalnego drzewa opinającego na ważonym grafie nieskierowanym przy użyciu podejścia zachłannego. W przypadku Algorytm Prima , wielokrotnie wybieramy wierzchołek, którego odległość od wierzchołka źródłowego jest zminimalizowana, czyli bieżący lokalnie optymalny wybór.

Biorąc to pod uwagę, czy algorytm Prim może mieć cykle?

Algorytm Prima . Algorytm Prima wyraźnie tworzy drzewo opinające, ponieważ nie cykl może być wprowadzone przez dodanie krawędzi między wierzchołkami drzewa i niedrzewa.

Który algorytm jest bardziej efektywny w konstruowaniu minimalnego drzewa rozpinającego danego grafu Algorytm Prima czy algorytm Kruskala i dlaczego?

Algorytm Kruskala rozwija rozwiązanie z najtańszej krawędzi, dodając następną najtańszą krawędź do istniejącej drzewo / Las. Algorytm Prima jest szybszy dla gęstych wykresy . Algorytm Kruskala jest szybszy dla rzadkich wykresy.

Zalecana: