Algorytm Kruskala

Z Wikipedii

Algorytm Kruskala wyznacza minimalne drzewo rozpinające. Jest to algorytm zachłanny, który wybiera krawędzie o najmniejszych wagach.

Opublikowany przez Josepha Kruskala w 1956 roku.

Spis treści 1 Algorytm 1 2 Algorytm 2 3 Zobacz też 4 Linki zewnętrzne

[edytuj] Algorytm 1

1. niech krawędzie będą uporządkowane następująco: C(e₁)C(e₂)...C(e_n); gdzie C: E -> R (funkcja wagowa)
2. dla każdego 1in: jeśli e_i nie tworzy cyklu w rozwiązaniu to dołącz do rozwiązania krawędź.

[edytuj] Algorytm 2

• Utwórz las L z wierzchołków oryginalnego grafu, gdzie każdy wierzchołek tworzy osobne drzewo.
• Utwórz zbiór S zawierający wszystkie krawędzie oryginalnego grafu.
• Dopóki S nie jest pusty:
  • Usuń z S krawędź o minimalnej wadze.
  • Jeśli usunięta krawędź łączyła dwa różne drzewa, to dodaj ją do lasu L, tak aby połączyła dwa odpowiadające drzewa w jedno
  • W przeciwnym wypadku, odrzuć ją.

Złożoność obliczeniowa: O(e*loge), gdzie e to liczba krawędzi.

[edytuj] Zobacz też

• przegląd zagadnień z zakresu matematyki

[edytuj] Linki zewnętrzne

• http://www.algorytm.org/index.php?option=com_content&task=view&id=100&Itemid=28