8063591573

Listing 2.4: (c.d. listingu z poprzedniej strony)

25    vector<Ve> g;

26    Graph(int n = 0) : g(n) { }

27    void EdgeD(int b, int e, E d = EO) {

28    g[b].PB(Ed(d, e));

29    }

30    void WriteO {

31    REP(x, SIZE(g)) {

32    cout << x << " : " ;

33    F0REACH(it, g[x]) cout « " " « it->v;

34    cout << endl;

35    }

36    }

37};

38    struct Empty { };

39    int mainO {

40    int n, m, b, e;

41    cin >> n » m;

42    Graph<Empty, Empty> gr (n) ;

43    REP(x, m) {

44    cin >> b >> e;

45    gr.EdgeD(b, e);

46    }

47    gr. WriteO;

48    return 0;

49}_

2.2. Przeszukiwanie grafu wszerz

Literatura
	WDA] - 23.2
	ASD] - 1.5.3
[KDP] - 2.3

BFS — czyli przeszukiwanie grafu wszerz (ang. breadth-first search), jest metodą, systematycznego badania struktury grafu. Zakłada ona, że dany jest graf G = (V, E) (skierowany bądź nieskie-rowany), oraz wyróżniony wierzchołek s, zwany źródłem przeszukiwania. Dla każdego wierzchołka v £ V, algorytm BFS oblicza odległość t(v) od wierzchołka s (rozumianą jako najmniejszą liczbę krawędzi na ścieżce od wierzchołka s do v). Wyznaczany jest również wierzchołek s(v) połączony krawędzią z v, przez który przechodzi najkrótsza ścieżka ze źródła wyszukiwania do v. Zasada działania algorytmu BFS jest prosta — na początku za odwiedzony wierzchołek uważa się tylko s — wyznaczona dla niego odległość to 0. Następnie przetwarzane są wierzchołki v, dla których odległość została już wyznaczona, w kolejności niemalejących odległości — dla każdego nie odwiedzonego sąsiada u wierzchołka v, przypisywane są wartości t(u) = t(v) + 1, s(u) = v. Na skutek wykonania algorytmu BFS, konstruowany jest las przeszukiwania wszerz, w skład którego wchodzą wszystkie wierzchołki osiągalne ze źródła wyszukiwania, oraz krawędzie konstruujące najkrótsze ścieżki (reprezentowane przez zmienne s(u)). Ze względu na fakt, iż nie wszystkie krawędzie grafu G muszą znajdować się w lesie przeszukiwania BFS, istnieje możliwość klasyfikacji krawędzi grafu G. Rozróżniane są następujące typy krawędzi, których definicja ma sens w przypadku rozpatrywania konkret-