AISDE LAB5

Zebrane pytania i odpowiedzi do zestawu. Lecimy

Ilość pytań: 7 Rozwiązywany: 1433 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 Boruvki:

na początku dokonuje sprawdzenia czy są cykle

Pytanie 4

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 5

Ogólne pytania:

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

Pytanie 6

Pytanie teoretyczne prawda/fałsz (1pkt) o 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 7

Algorytm Dijkstry nie nadaje sie do szukania najkrotszych sciezek

działać dla krawędzi o ujemnych wagach

w grafach zawierajacych cykle