Kopia DSC00538

Wstęp do aigorytmizacji

l. Dla skierowanego grafu ważonego o N węzłach, którego struktura jest znana w postaci macierzy Incydencji G napisać pseudokod algorytmu, który wyznacza dowolną ścieżkę między wskazanymi węzłami: źródłowym S i docelowym T (jednym). Ponadto algorytm powinien zwracać informację o długości tej ścieżki (rozumianej jako suma wag krawędzi ją tworzących, oraz o wadze krawędzi, która w tej ścieżce ma wagę najmniejszą. Można wykorzystać jako punkt wyjścia jeden z algorytmów utworzonych w ramach zajęć ćwiczeniowych. Przyjąć „naturalny" sposób etykietowania węzłów grafu, tzn.: „I”, „2”.....„N”.

Przekształcić poniższy pseudokod algorytmu Euklidesa służącego do wyznaczania największego wspólnego dzielnika pary nieujemnych liczb całkowitych a i b tak, by zwracana była wartość najmniejszej wspólnej wielokrotności tej samej pary liczb, int Euklid(a, b)

{

i£ (a < b)

• b; if (b - 0) return (0); while (b * 0) do {

r <- a mod b; a <— b; b <— r;

I

return (a) ,*

)

3j Na tys. (a) pokazany jest graf z wagami, a na rysunkach (b) i (c) pokazane są dwa różne sposoby oznaczenia etykietami jego krawędzi za pomocą liter o, b,.... n w kolejności rosnących wag.

(a)    Zastosuj algorytm Kruskala do grafu o krawędziach uporządkowanych tak jak na rys. (b). Narysuj otrzymane minimalne drzewo spinające i podaj jego wagę.

(b)    Powtórz zadanie (a), kiedy krawędzie sa uporządkowane tak, jak na rysunku (c).

II

(a)

Uli

UDi

240
V
	i

<b)

(e)

i