8063591570

Jako zadanie „rozgrzewkowe”, napiszemy prostą funkcję wypisującą strukturę grafu na standardowe wyjście. Na początku każdego wiersza opisu powinien znaleźć się numer kolejnego wierzchołka (zaczynając numerację od 0), a następnie lista wierzchołków, z którymi ten wierzchołek jest połączony krawędzią. Przykładowa implementacja tej funkcji przedstawiona jest na listingu 2.2.

Listing 2.2: Implementacja funkcji void Graph<V,E>: :WriteO

1    void WriteO {

// Dla wszystkich wierzchołków w grafie zaczynając od 0...

2    REP(x, SIZE(g)) {

// Wypisz numer wierzchołka

3    cout << x << ":";

// Dla każdej krawędzi wychodzącej z przetwarzanego wierzchołka o numerze // x, wypisz numer wierzchołka, do którego ona prowadzi

4    F0REACH(it, g[x]) cout << " " << it->v;

5    cout « endl;

6    }

JO_

Załóżmy, że w pliku znajduje się opis grafu skierowanego w następującym formacie: w pierwszym wierszu zapisane są dwie liczby naturalne — nim, oznaczające odpowiednio liczbę wierzchołków, oraz krawędzi w grafie (wierzchołki numerowane są od 0 do n — 1). W kolejnych m wierszach umieszczone są po dwie liczby naturalne b i e, oznaczające, że z wierzchołka o numerze b prowadzi krawędź skierowana do wierzchołka o numerze e. Chcemy napisać program, który przekonwertuje opis tego grafu na format, jaki jest generowany przez funkcję void Graph<V,E>: :WriteO.

Dla następującego opisu wejściowego:

5 8 0 1

3    4

4    1 4 0 1 2

2    4

3    2

4    3

Program wygeneruje następujący wynik:

Rozwiązanie jest proste — wystarczy wykorzystać strukturę Graph<V,E>, na podstawie opisu z pliku skonstruować odpowiedni graf, a następnie wypisać jego strukturę przy użyciu funkcji void Graph::WriteO. Główna część programu, realizującego to zadanie, przedstawiona jest na listingu 2.3. Pominięte w nim zostały standardowe nagłówki pochodzącego z biblioteczki. Właśnie w ten sposób, w dalszej części książki, będą prezentowane przykładowe programy. Z uwagi na fakt, iż omówiony tu przykład jest pierwszym kompletnym programem, jaki do tej pory udało nam się stworzyć, zatem na listingu 2.4 zamieszczony jest pełny kod źródłowy tego programu. W dalszych rozdziałach książki po pełny kod źródłowy programów należy sięgać do załączonej płyty.