Ścieżki z Wierzchołka

Wstęp

Jednym z zastosowań algorytmu BFS jest możliwość napisania programy, który wypisze ścieżki z wskazanego wierzchołka do wszystkich pozostałych wierzchołków w grafie. W tym artykule zostanie wyjaśnione jak napisać taki kod.

Przykład

Przykładowo dany jest graf:

Przykładowy Graf

Program powinien wtedy wypisać na konsolę, że:

1. A: start
2. B: A > B
3. C: A > C
4. D: A > D
5. E: A > B > E
6. F: A > C > F
7. G: brak
8. H: brak

Podane ścieżki są przykładowe i należy pamiętać, że do niektórych wierzchołków istnieje więcej niż jedna ścieżka o minimalnej długości tj. do F można dojść A > C > F lub A > D > F. Wszystko zależy od wybranej metody przechodzenia BFS. Należy jednak pamiętać, że zawsze należy wypisać najkrótszą ścięzkę, więc przykładowo A > B > E > F nie byłaby już poprawna skoro istnieją ścieżki o długości 2.

Implementacja

Zadanie zostaje podzielona na dwa etapy: pierwszy polega na wyznaczeniu tablicy, gdzie zostaną zapisane informacje o przodku i odległości dla każdego wierzchołka. Drugi etap pozwoli zinterpretować te dane i wypisać na ich podstawie szukane ścieżki. Poniżej została przedstawiona funkcja BFS(), która dla danej macierzy oraz wierzchołka początkowego start wyznaczy szukaną tablicę. Dokładny opis algorytmu można znaleźć tutaj.

1. dane* BFS(int** macierz, int n, int start) {
2.   dane* tab = new dane[n];
3.   for (int i = 0; i < n; i++) {
4.     tab[i].odleglosc = INT32_MAX;
5.     tab[i].poprzednik = -1;
6.   }
7.   tab[start].odleglosc = 0;
8.   queue<int> q;
9.   q.push(start);
10.   while (q.size() != 0) {
11.     int u = q.front();
12.     q.pop();
13.     for (int i = 0; i < n; i++) {
14.       if (macierz[u][i] > 0 && tab[i].odleglosc == INT32_MAX) {
15.         tab[i].odleglosc = tab[u].odleglosc + 1;
16.         tab[i].poprzednik = u;
17.         q.push(i);
18.       }
19.     }
20.   }
21.   return tab;
22. }

Z kolei druga funkcja WypiszDane() interpretuje zebrane informacje.

1. void WypiszDane(dane* tab, int n, int start) {
2.   for (int i = 0; i < n; i++) {
3.     cout << i << ": ";
4.     if (i == start) {
5.       cout << "start";
6.     }
7.     else
8.     {
9.       if (tab[i].odleglosc == INT32_MAX) {
10.         cout << "nieosiagalny";
11.       }
12.       else
13.       {
14.         vector<int> sciezka;
15.         sciezka.push_back(i);
16.         int q = i;
17.         while (q != start) {
18.           q = tab[q].poprzednik;
19.           sciezka.push_back(q);
20.         }
21.         cout << start;
22.         for (int j = sciezka.size() - 2; j >= 0; j--) {
23.           cout << " > " << sciezka[j];
24.         }
25.       }
26.     }
27.     cout << endl;
28.   }
29. }

Podczas interpretacji rozpoznajemy trzy możliwe stany: wierzchołek jest wierzchołkiem startowym, albo jest nieosiągalny. Trzecia możliwość to wierzchołek jest osiągalny i chcemy wypisać ścieżkę. Do wyznaczenia ścieżki należy od sprawdzanego wierzchołka sprawdzać jego przodków, a potem przodków, przodków, itd. Poszukiwanie ścieżki kończy się po osiągnięciu wierzchołka startowego.

Testowanie funkcji

Do przetestowania kodu można skorzystać z poniższego fragment programu. Wczytuje on macierz reprezentującą graf oraz wierzchołek podstawowy.

1. int main() {
2.   int n, s;
3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
4.   cin >> n;
5.   cout << "Podaj wezel poczatkowy\n s = ";
6.   cin >> s;
7.   int** macierz = new int*[n];
8.   for (int i = 0; i < n; i++) {
9.     macierz[i] = new int[n];
10.     for (int j = 0; j < n; j++) {
11.       cin >> macierz[i][j];
12.     }
13.   }
14.   dane* tab = BFS(macierz, n, s);
15.   cout << "\nDostepne sciezki:" << endl;
16.   WypiszDane(tab, n, s);
17.   system("pause");
18.   return 0;
19. }

• Kod źródłowy Implementacja