Strona główna » Algorytmy » Artykuły » Algorytm Prima
 

Algorytm Prima

https://mattomatti.com/a0146

Opis

Algorytma Prima pozwala znaleźć w grafie nieskierowanym minimalne drzewo rozpinające. Każda z krawędzi musi mieć określoną wagę. To na podstawie tych wartości algorytm będzie dopasowywał je do drzewa. Punktem początkowym może być dowolny wierzchołek grafu. Innymi słowy minimalne drzewo rozpinające uzyskane na końcu zawsze będzie takie samo dla tego samego grafu.

Algorytm

Dla każdego wierzchołka określamy, że jego koszt wynosi nieskończoność, a poprzednik jest nieokreślony. Wybranemu wierzchołkowi przypisujemy wartość 0, a następnie tworzymy kolejkę wierzchołków do rozpatrzenia. W kolejce dane są posortowane po koszcie elementu. Następnie, dopóki kolejka nie jest pusta, wybieramy wierzchołek o najniższym koszcie i aktualizujemy jego sąsiadów, którzy występują w kolejce. Jeśli krawędź z wybranego wierzchołka z kolejki do sąsiada ma niższą wartość niż sąsiad ma koszt to aktualizujemy informacje.

Przykład

Rozpatrzmy następujący graf:

Przykładowy graf

Zgodnie z algorytmem najpierw utwórzmy dla każdego wierzchołka parę danych: koszt i poprzednika. Szukamy drzewa rozpoczynając od wierzchołka 0.

Kolejka012345WybranyKomentarz
0, 1, 2, 3, 4, 50 | -1∞ | -1∞ | -1∞ | -1∞ | -1∞ | -10Usuwamy 0 z kolejki i aktualizujemy sąsiadów
1, 2, 3, 4, 50 | -14 | 05 | 0∞ | -1∞ | -1∞ | -11Najmniejszy koszt wierzchołek 1
2, 3, 4, 50 | -14 | 03 | 14 | 1∞ | -1∞ | -12Najmniejszy koszt wierzchołek 2
3, 4, 50 | -14 | 03 | 12 | 26 | 21 | 25Najmniejszy koszt wierzchołek 5
3, 40 | -14 | 03 | 12 | 25 | 51 | 23Najmniejszy koszt wierzchołek 3
30 | -14 | 03 | 12 | 24 | 31 | 24Najmniejszy koszt wierzchołek 4
-0 | -14 | 03 | 12 | 24 | 31 | 2-Kolejka pusta, koniec algorytmu

Dla każdego wierzchołka zostały otrzymane dwie wartości. Pierwsza z nich określa koszt wierzchołka. Suma tej wartości dla wszystkich wierzchołków da łączną wartość minimalnego drzewa rozpinającego. W tym przypadku wynosi ona 14. Z kolei druga wartość poprzednik pozwala określić, które węzły są ze sobą połączone. W tym przypadku warto pamiętać, że graf nie jest skierowany. Na podstawie otrzymanych danych można narysować następujące minimalne drzewo rozpinające:

Minimalne drzewo rozpinające graf

Analiza złożoności

Złożoność algorytmu jest zależna od implementacji kolejki. Niemniej wewnątrz algorytmu przechodzimy po wszystkich n elementach kolejki i za każdym razem aktualizujemy n sąsiadów. Oznacza to, że sam algorytm ma złożoność O(n2). Jednak należy pamiętać, że dodatkowo w każdej pętli należy uaktualnić kolejkę priorytetową, albo przeszukiwać listę w celu znalezienia minimalnego elementu.

Implementacja

Założenia

Algorytm otrzymuje jako argumeny macierz sąsiedztwa grafu, a w wyniku zwraca parę danych: koszt i poprzednik dla każdego wierzchołka. Program nie sprawdza poprawności danych wejściowych. W celu wczytania przykładowego grafu należy podać go w następujący sposób:

  1. 0 4 5 0 0 0
  2. 4 0 3 4 0 0
  3. 5 3 0 2 6 1
  4. 0 4 2 0 4 2
  5. 0 0 6 4 0 5
  6. 0 0 1 2 5 0

Algorytm

Funkcja AlgorytmPrima() spełnia opisane wyżej założenia. W celu wyszukiwania minimalnego elementu w kolejce wykorzystuje wyszukiwanie.

C++C#
Python
  1. def AlgorytmPrima(macierz, s):
  2.   n = len(macierz)
  3.   wynik = [dane() for x in range(n)];
  4.   wynik[s].koszt = 0
  5.   kolejka = list(range(n))
  6.   while (len(kolejka) != 0):
  7.     u = -1
  8.     for q in kolejka:
  9.       if (wynik[q].koszt != sys.maxsize and
  10.         (u == -1 or wynik[q].koszt < wynik[u].koszt)):
  11.         u = q;
  12.     for j in range(n):
  13.       try:
  14.         kolejka.index(j)
  15.         if (macierz[u][j] == 0):
  16.           continue
  17.       except ValueError:
  18.         continue
  19.       if (wynik[j].koszt > macierz[u][j]):
  20.         wynik[j].koszt = macierz[u][j]
  21.         wynik[j].poprzednik = u
  22.     kolejka.remove(u)
  23.     print(str(u))
  24.   return wynik

(3.) Utwórz miejsce do zapisu wyniku oraz (4.) przypisz pierwszemu wierzchołkowi zerowy koszt. Następnie (5.) utwórz kolejkę i (6.) operuj na niej, aż zostanie pusta. (7. - 10.) Znajdź element w kolejce o najniższym koszcie. Potem (11.) dla każdego jego sąsiada: (12. - 17.) sprawdź czy istnieje pomiędzy nimi krawędź i czy sąsiad jest w kolejce oraz (18.) czy koszt trzeba zaktualizować. Jeśli tak to (21. - 22.) należy to wykonać. Na koniec pętli (23.) należy pamiętać o usunięciu wybranego z kolejki elementu! Na koniec zwracana jest wyznaczona tablica wynik.

Testowanie funkcji

W celu przetestowania działania napisanej funkcji można skorzystać z poniższego fragmentu kodu:

C++C#
Python
  1. n = int(input("Ile wierzchołków ma graf?\n n = "))
  2. s = int(input("Od którego wierzchołka zacząć?\n s = "))
  3. print("Podaj macierz:")
  4. macierz = [[int(x) for x in input().split()] for y in range(n)]
  5. wynik = AlgorytmPrima(macierz, s)
  6. suma = 0
  7. print("ID\tPoprzednik")
  8. for i in range(n):
  9.   print(str(i) + "\t" + str(wynik[i].poprzednik))
  10.   suma += wynik[i].koszt
  11. print("Łączny koszt wynosi: " + str(suma))