Ś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. static dane[] BFS(int[,] macierz, int start)
2. {
3. dane[] tab = new dane[macierz.GetLength(0)];
4. for (int i = 0; i < macierz.GetLength(0); i++)
5. {
6. tab[i].odległość = int.MaxValue;
7. tab[i].poprzednik = -1;
8. }
9. tab[start].odległość = 0;
10. Queue<int> q = new Queue<int>();
11. q.Enqueue(start);
12. while (q.Count != 0)
13. {
14. int u = q.Dequeue();
15. for (int i = 0; i < macierz.GetLength(0); i++)
16. {
17. if (macierz[u, i] > 0 && tab[i].odległość == int.MaxValue)
18. {
19. tab[i].odległość = tab[u].odległość + 1;
20. tab[i].poprzednik = u;
21. q.Enqueue(i);
22. }
23. }
24. }
25. return tab;
26. }

Z kolei druga funkcja WypiszDane() interpretuje zebrane informacje.

1. static void WypiszDane(dane[] tab, int start)
2. {
3. for (int i = 0; i < tab.Length; i++)
4. {
5. Console.Write("{0}: ", i);
6. if (i == start)
7. {
8. Console.Write("start");
9. }
10. else
11. {
12. if (tab[i].odległość == int.MaxValue)
13. {
14. Console.Write("nieosiągalny");
15. }
16. else
17. {
18. List<int> sciezka = new List<int>();
19. sciezka.Add(i);
20. int q = i;
21. while (q != start)
22. {
23. q = tab[q].poprzednik;
24. sciezka.Add(q);
25. }
26. Console.Write(start);
27. for (int j = sciezka.Count - 2; j >= 0; j--)
28. {
29. Console.Write(" > {0}", sciezka[j]);
30. }
31. }
32. }
33. Console.WriteLine();
34. }
35. }

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. static void Main(string[] args)
2. {
3. Console.Write("Podaj ile jest wierzchołków w grafie\n n = ");
4. int n = Convert.ToInt32(Console.ReadLine());
5. Console.Write("Podaj węzeł początkowy\n s = ");
6. int s = Convert.ToInt32(Console.ReadLine());
7. int[,] macierz = new int[n, n];
8. for (int i = 0; i < n; i++)
9. {
10. string[] str = Console.ReadLine().Split(' ');
11. for (int j = 0; j < n; j++)
12. {
13. macierz[i, j] = Convert.ToInt32(str[j]);
14. }
15. }
16. dane[] tab = BFS(macierz, s);
17. Console.WriteLine("Węzeł\tOdl.\tPoprzednik");
18. WypiszDane(tab, s);
19. Console.ReadKey();
20. }

• Kod źródłowy Implementacja