Pytania i odpowiedzi

aisde lab 5

Zebrane pytania i odpowiedzi do zestawu. wejście
Ilość pytań: 6 Rozwiązywany: 1148 razy
Pytanie 1
Algorytm Prima:
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
Pytanie 2
Algorytm Kruskala:
jego złożoność obliczeniowa zależy od ilości krawędzi
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
Pytanie 3
Algorytm Floyda:
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
Pytanie 4
Algorytm Kruskala:
ma złożoność obliczeniową zależną od liczby krawędzi grafu
Przed dodaniem każdej krawędzi wymaga sprawdzenia, czy nie powstanie cykl
Pytanie 5
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
Pytanie 6
Algorytm Dijkstry nie nadaje sie do szukania najkrotszych sciezek:
w grafach zawierajacych cykle

Powiązane tematy