aisde lab 5

Zebrane pytania i odpowiedzi do zestawu. wejście

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