AISDE LAB5

Lecimy

7 pytań Strona 1 szary7
Algorytm Prima:
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
jego złożoność obliczeniowa zależy od ilości krawędzi
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
Algorytm Kruskala:
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
jego złożoność obliczeniowa zależy od ilości krawędzi
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
Algorytm Boruvki:
na początku dokonuje sprawdzenia czy są cykle
nie działa, gdy są cykle
działa tylko dla grafów skierowanych
tworzy drzewo Steinera
Algorytm Floyda w stosunku do Dijkstry:
- może działać dla krawędzi o ujemnych wagach
- może znajdować długości cykli
może działać nieprawidłowo dla grafu o wagach dodatnich nienaturalnych
- działa niezależnie od liczby krawędzi grafu
Ogólne pytania:
macierz sąsiedztwa ma wymiar VxE, dla V-liczba wierzchołków, E-liczba krawędzi
złożoność pamięciowa Floyda wynosi V^2
graf niepełny nieskierowany ma max V*(V-1)/2 krawędzi
gdy wszystkie wagi grafu są różne, to istnieje tylko 1 drzewo rozpinające
Dalej
Pozostała 1 strona