Fiszki

aisde lab 5

Test w formie fiszek wejście
Ilość pytań: 6 Rozwiązywany: 1397 razy
Algorytm Prima:
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
Algorytm Kruskala:
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
Algorytm Floyda:
czy algorytm po skonczeniu dzialania daje w wyniku dlugosci cykli
czy wagi NIE moga byc ujemne
czy najlepiej implementowac na macierzy
czy czas trwania algorytmu zalezy bardziej od wiercholkow niz krawedzi
czy algorytm po skonczeniu dzialania daje w wyniku dlugosci cykli
czy najlepiej implementowac na macierzy
czy czas trwania algorytmu zalezy bardziej od wiercholkow niz krawedzi
Algorytm Kruskala:
ma złożoność obliczeniową zależną od liczby krawędzi grafu
konsekwentnie dodaje krawędzie do jednego drzewa, aż stanie się ono drzewem rozpinającym
Przed dodaniem każdej krawędzi wymaga sprawdzenia, czy nie powstanie cykl
Algorytm polega na usuwaniu z grafu krawędzi o najwyższej wadze tak długo, aż zostanie drzewo rozpinające
ma złożoność obliczeniową zależną od liczby krawędzi grafu
Przed dodaniem każdej krawędzi wymaga sprawdzenia, czy nie powstanie cykl
Algorytm Floyda w stosunku do DIjkstry
może działać dla krawędzi o ujemnych wagach
może znajdować długości cykli
działa niezależnie od liczby krawędzi grafu
może działać nieprawidłowo dla grafu o wagach dodatnich nienaturalnych
może działać dla krawędzi o ujemnych wagach
może znajdować długości cykli
działa niezależnie od liczby krawędzi grafu
Algorytm Dijkstry nie nadaje sie do szukania najkrotszych sciezek:
w grafach skierowanych
w grafach planarnych
w grafach zawierajacych cykle
w grafach zawierajacych cykle

Powiązane tematy

Inne tryby