Przechodzenie przez wykres
Przechodzenie przez wykres oznacza odwiedzanie każdego wierzchołka i krawędzi dokładnie raz w studni -zdefiniowana kolejność. Korzystając z niektórych algorytmów grafowych, należy upewnić się, że każdy wierzchołek grafu jest odwiedzany dokładnie raz. Kolejność odwiedzania wierzchołków jest ważna i może zależeć od algorytmu lub pytania, które rozwiązujesz.
Podczas przemierzania ważne jest, aby śledzić, które wierzchołki zostały odwiedzone. Najpopularniejszym sposobem śledzenia wierzchołków jest ich oznaczanie.
Breadth First Search (BFS)
Istnieje wiele sposobów przechodzenia przez wykresy. BFS jest najczęściej stosowanym podejściem.
BFS to algorytm przechodzenia, w którym należy rozpocząć przechodzenie od wybranego węzła (węzła źródłowego lub początkowego) i przechodzić przez warstwę grafu, eksplorując w ten sposób sąsiednie węzły (węzły, które są bezpośrednio połączone z węzłem źródłowym). Następnie musisz przejść do węzłów sąsiednich następnego poziomu.
Jak sugeruje nazwa BFS, musisz przejść przez wykres wszerz w następujący sposób:
- Najpierw przejdź w poziomie i odwiedź wszystkie węzły bieżącej warstwy
- Przejdź do następnej warstwy
Rozważ poniższy diagram. 
Odległość między węzłami w warstwie 1 jest porównywalnie mniejsza niż odległość między węzłami w warstwie 2. Dlatego w BFS musisz przejść przez wszystkie węzły w warstwie 1, zanim przejdziesz do węzłów w warstwie 2.
Przechodzenie przez węzły potomne
Graf może zawierać cykle, które mogą doprowadzić Cię ponownie do tego samego węzła podczas przechodzenia przez wykres. Aby uniknąć ponownego przetwarzania tego samego węzła, użyj tablicy logicznej, która oznacza węzeł po przetworzeniu. Odwiedzając węzły w warstwie wykresu, przechowuj je w taki sposób, aby można było przechodzić przez odpowiednie węzły potomne w podobnej kolejności.
Aby ułatwić ten proces, użyj kolejki do przechowywania węzła i oznacz go jako „odwiedzony”, dopóki wszystkie jego sąsiedzi (wierzchołki, które są bezpośrednio z nim połączone) nie zostaną zaznaczone. Kolejka działa zgodnie z metodą kolejkowania First In First Out (FIFO), w związku z czym sąsiedzi węzła będą odwiedzani w kolejności, w jakiej zostały wstawione do węzła, tj. Węzeł, który został wstawiony jako pierwszy, będzie odwiedzany jako pierwszy, a więc na.
Pseudokod
Proces przemierzania 
Przemieszczanie rozpocznie się od węzła źródłowego i umieści w kolejce. s zostaną oznaczone jako „odwiedzone”.
Pierwsza iteracja
- s zostaną pobrane z kolejki
- Sąsiedzi s ie 1 i 2 będą przemierzani
- 1 i 2, które wcześniej nie zostały pokonane, są pokonane. Będą one:
- Umieszczone w kolejce
- 1 i 2 zostaną oznaczone jako odwiedzone
Druga iteracja
- 1 jest pobierane z kolejki
- Sąsiedzi z 1 tj. s i 3 są przechodzeni
- s jest ignorowany, ponieważ jest oznaczony jako „odwiedzony”
- 3, który nie został przekroczony wcześniej, został przekroczony. Jest:
- Wstawiono do kolejki
- Oznaczono jako odwiedzone
Trzecia iteracja
- 2 jest pobierane z kolejki
- Sąsiedzi z 2 tj. s, 3 i 4 są przemierzani
- 3 i s są ignorowane, ponieważ są oznaczani jako „odwiedzeni”
- 4, przez który nie przeszedł wcześniej, został przekroczony. Jest:
- Wstawiono do kolejki
- Oznaczono jako odwiedzone
Czwarta iteracja
- 3 jest pobierane z kolejki
- Sąsiedzi 3, tj. 1, 2 i 5 są przemierzani
- 1 i 2 są ignorowani, ponieważ są oznaczani jako „odwiedzeni”
- 5, przez który nie przeszedł wcześniej, został przekroczony. Jest:
- Wstawiono do kolejki
- Oznaczono jako odwiedzone
Piąta iteracja
- 4 zostaną usunięte z kolejki
- Sąsiedzi z 4, tj. 2 jest przesuwane
- 2 jest ignorowane, ponieważ jest już oznaczone jako „odwiedzone”
Szósta iteracja
- 5 jest pobierane z kolejki
- Sąsiedzi z 5, czyli 3 jest przemierzany
- 3 jest ignorowane, ponieważ jest już oznaczona jako „odwiedzona”
Kolejka jest pusta i wychodzi z pętli. Wszystkie węzły zostały pokonane przy użyciu BFS.
Jeśli wszystkie krawędzie na wykresie mają taką samą wagę, wówczas BFS można również użyć do znalezienia minimalnej odległości między węzłami na wykresie.
Przykład
Tak jak na tym diagramie, zacznij od węzła źródłowego, aby znaleźć odległość między źródłem węzeł i węzeł 1. Jeśli nie zastosujesz się do algorytmu BFS, możesz przejść od węzła źródłowego do węzła 2, a następnie do węzła 1. To podejście obliczy odległość między węzłem źródłowym a węzłem 1 jako 2, podczas gdy minimalna odległość wynosi w rzeczywistości 1. Minimalną odległość można poprawnie obliczyć za pomocą algorytmu BFS.
Złożoność
Złożoność czasowa BFS wynosi O (V + E), gdzie V to liczba węzłów, a E to liczba krawędzi.
Aplikacje
1. Jak określić poziom każdego węzła w danym drzewie?
Jak wiesz w BFS, przemierzasz poziom. Możesz również użyć BFS do określenia poziomu każdego węzła.
Implementacja
Ten kod jest podobny do kodu BFS z tylko następującą różnicą:
poziom] = poziom + 1;
W tym kodzie, podczas odwiedzania każdego węzła, poziom tego węzła jest ustawiany wraz ze wzrostem poziomu jego węzła nadrzędnego. W ten sposób określany jest poziom każdego węzła.
2 . 0-1 BFS
Ten typ BFS jest używany do znalezienia najkrótszej odległości między dwoma węzłami na wykresie pod warunkiem, że krawędzie wykresu mają wagi 0 lub 1. Jeśli zastosujesz BFS wyjaśnione wcześniej w w tym artykule otrzymasz niepoprawny wynik dla optymalnej odległości między 2 węzłami.
W tym podejściu tablica boolowska nie jest używana do oznaczania węzła, ponieważ warunek optymalnej odległości zostanie sprawdzony, gdy odwiedź każdy węzeł. Do przechowywania węzła używana jest podwójna kolejka. W 0-1 BFS, jeśli waga krawędzi = 0, to węzeł jest wypychany na przód dekolejki. Jeśli waga krawędzi = 1, to węzeł jest wypychany do tyłu dekolejki.
Implementacja
Q to kolejka z dwoma końcami. Odległość to tablica, w której odległość będzie zawierać odległość od węzła początkowego do v węzła. Początkowo odległość zdefiniowana od węzła źródłowego do każdego węzła to nieskończoność.
Zrozummy ten kod za pomocą następującego wykresu:
Lista sąsiedztwa wykresu będzie wyglądać następująco:
Tutaj „s” jest uważane za 0 lub węzeł źródłowy.
0 – > 1 – > 3 – > 2
edge.first = 1, edge.second = 1
edge.first = 3, edge.second = 0
edge.first = 2, edge.second = 1
1 – > 0 – > 4
edge.first = 0, edge.second = 1
edge.first = 4 , edge.second = 0
2 – > 0 – > 3
edge.first = 0 , edge.second = 0
edge.first = 3, edge.second = 0
3 – > 0 – > 2 – > 4
edge.first = 0, edge.second = 0
edge.first = 2, edge.second = 0
edge.first = 4, edge.second = 0
4 – > 1 – > 3
edge.first = 1, edge.second = 0
edge.first = 3, edge.second = 0
Jeśli użyjesz algorytmu BFS, wynik będzie niepoprawny, ponieważ pokaże ci optymalna odległość między s a węzeł 1 i si węzeł 2 odpowiednio jako 1. Dzieje się tak, ponieważ odwiedza dzieci si oblicza odległość między s i jego dziećmi, która wynosi 1. Rzeczywista optymalna odległość wynosi 0 w obu przypadkach.
Przetwarzanie
Zaczynając od węzła źródłowego, tj. 0, przesunie się w kierunku 1, 2 i 3. Ponieważ waga krawędzi między 0 a 1 i 0 i 2 wynosi odpowiednio 1 , 1 i 2 zostaną przesunięte na koniec kolejki. Jednakże, ponieważ waga krawędzi między 0 a 3 wynosi 0, 3 zostanie przesunięte na początek kolejki. Odległość będzie odpowiednio utrzymywana w tablicy odległości.
3 zostanie wtedy wyskoczony z kolejki i ten sam proces zostanie zastosowany do sąsiadów itd.