Strona główna » Algorytmy » Artykuły » Ścieżki z Wierzchołka
 

Ścieżki z Wierzchołka

https://mattomatti.com/a0260

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.

C++C#
Python
  1. def BFS(macierz, start):
  2. tab = []
  3. for i in range(0, len(macierz)):
  4. tab.append(dane(sys.maxsize, -1))
  5. tab[start].odległość = 0
  6. q = queue.Queue()
  7. q.put(start)
  8. while (not q.empty()):
  9. u = q.get()
  10. for i in range(0, len(macierz)):
  11. if (macierz[u][i] > 0 and tab[i].odległość == sys.maxsize):
  12. tab[i].odległość = tab[u].odległość + 1
  13. tab[i].poprzednik = u
  14. q.put(i)
  15. return tab

Z kolei druga funkcja WypiszDane() interpretuje zebrane informacje.

C++C#
Python
  1. def wypiszDane(tab, start):
  2.   for i in range(len(tab)):
  3.     print(str(i) + ": ", end="")
  4.     if (i == start):
  5.       print("start", end="")
  6.     else:
  7.       if (tab[i].odległość == sys.maxsize):
  8.         print("nieosiągalny", end="")
  9.       else:
  10.         sciezka = []
  11.         sciezka.append(i)
  12.         q = i
  13.         while q != start:
  14.           q = tab[q].poprzednik
  15.           sciezka.append(q)
  16.         print(start, end="")
  17.         for j in range(len(sciezka) - 2, -1, -1):
  18.           print(" >", sciezka[j], end="")
  19.     print()

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.

C++C#
Python
  1. n = int(input('Podaj ile węzłów ma graf\n n = '))
  2. s = int(input('Podaj węzeł startowy\n s = '))
  3. print('Podaj elementy macierzy:')
  4. macierz = []
  5. for i in range(0, n):
  6. tab = [int(x) for x in input().split()]
  7. macierz.append(tab)
  9. tab = BFS(macierz, s)
  10. wypiszDane(tab, s)