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)

Wyszukiwarka

Podobne podstrony:
Kopia DSC00538 Wstęp do aigorytmizacji l. Dla skierowanego grafu ważonego o N węzłach, którego struk
Kopia DSC00537 I . tita skierowanego grafu ważonego o N węzłach, którego struktura jest znana w post
1 Okładka 2 KRÓTKIE WYKŁADYi { M K O l Wstęp do językoznawstv dla studentów kierunków i Biblioteka P
1 Okładka KRÓTKIEWYKŁADYJ(Z V K 0 Biblioteka Pedayo w Sienid n 114860 Wstęp do językoznawstv dla stu
Lightbot - gładki wstęp do programowania dla najmłodszych Dlaczego akurat Lightbot? W Lightbot
SDC14146 Spis treści Wprowadzenie /11 Rozdział 1 Wstęp do badań marketingowych, czyli badać czy nie
wstęp do teorii polityki img 132 141 wmętrznątrcściątego atrybutu podmiotowego1 1. Jest ona bowiem p
wstęp do teorii polityki img 175 165 Kryterium współcześnie najważniejszym jest poziom rozwoju ekono
P2210359 58 Wstęp do historii filozofii 3. Wnioski dotyczące pojęcia filozofii Skoro filozofia jest
Edward Radosiński Wstęp do analizy finansowej W tej książce przyjęto, że analiza finansowa jest
Wstęp do Metod Sztucznej Inteligencji wybranej prostej, po czym stosowana jest metoda gradientowa w
się bał, że słowa jego dojdą do uszu, dla których były przeznaczone: -Marnością nad marnościami jest
IMG88 56 W: Struktura modelu poznania. Dla naszej epoki czymś centralnym wydaje struktura. Jest to
27 PŁOCKIE, 19. cznie później: dla tego, jeśli ruska grafika, ile dziś jest znana, znaczną onych

więcej podobnych podstron