Przechodzenie przez wykres — Graph traversal
W informatyce , przechodzenie wykres (znany również jako poszukiwanie milimetrowym ) odnosi się do procesu wizyty (sprawdzanie i / lub aktualizacji) każdy wierzchołek w wykresie . Takie przejścia są klasyfikowane według kolejności odwiedzania wierzchołków. Przechodzenie przez drzewo jest szczególnym przypadkiem przechodzenia przez graf.
Nadmierność
W przeciwieństwie do przemierzania drzewa, przemierzanie grafu może wymagać, aby niektóre wierzchołki były odwiedzane więcej niż raz, ponieważ niekoniecznie wiadomo przed przejściem do wierzchołka, który został już zbadany. Gdy wykresy stają się bardziej gęste , ta nadmiarowość staje się bardziej powszechna, powodując wydłużenie czasu obliczeń; gdy wykresy stają się coraz rzadsze, sytuacja jest odwrotna.
Dlatego zwykle konieczne jest zapamiętanie, które wierzchołki zostały już zbadane przez algorytm, aby wierzchołki były ponownie odwiedzane tak rzadko, jak to możliwe (lub w najgorszym przypadku, aby zapobiec kontynuowaniu przemierzania w nieskończoność). Można to osiągnąć przez powiązanie każdego wierzchołka grafu ze stanem „koloru” lub „wizytacji” podczas przechodzenia, który jest następnie sprawdzany i aktualizowany, gdy algorytm odwiedza każdy wierzchołek. Jeśli wierzchołek został już odwiedzony, jest ignorowany, a ścieżka nie jest kontynuowana; w przeciwnym razie algorytm sprawdza/aktualizuje wierzchołek i kontynuuje swoją bieżącą ścieżką.
Kilka szczególnych przypadków grafów implikuje wizytację innych wierzchołków w ich strukturze, a zatem nie wymaga, aby wizytacja była wyraźnie rejestrowana podczas przechodzenia. Ważnym tego przykładem jest drzewo: podczas przechodzenia można założyć, że wszystkie wierzchołki „przodka” bieżącego wierzchołka (i inne w zależności od algorytmu) zostały już odwiedzone. Zarówno przeszukiwanie grafów w głąb, jak i wszerz to adaptacje algorytmów opartych na drzewie, wyróżniające się przede wszystkim brakiem strukturalnie określonego wierzchołka „głównego” oraz dodaniem struktury danych do rejestrowania stanu odwiedzin przemierzania.
Algorytmy przechodzenia grafów
Notatka. — Jeśli przez każdy wierzchołek grafu ma przechodzić algorytm oparty na drzewie (taki jak DFS lub BFS), algorytm musi być wywołany co najmniej raz dla każdego połączonego składnika grafu. Można to łatwo osiągnąć, wykonując iterację przez wszystkie wierzchołki grafu, wykonując algorytm na każdym wierzchołku, który jest nadal nieodwiedzany podczas badania.
Wyszukiwanie w głąb
Przeszukiwanie w głąb (DFS) to algorytm przechodzenia przez skończony graf. DFS odwiedza wierzchołki dziecka przed odwiedzeniem wierzchołków rodzeństwa; to znaczy, że przemierza głębokość każdej konkretnej ścieżki przed zbadaniem jej szerokości. Stos (często stos wywołań programu za pośrednictwem rekursji ) jest zwykle używany podczas implementacji algorytmu.
Algorytm rozpoczyna się od wybranego wierzchołka „głównego”; następnie iteracyjnie przechodzi z bieżącego wierzchołka do sąsiedniego, nieodwiedzanego wierzchołka, dopóki nie może już znaleźć niezbadanego wierzchołka, do którego ma przejść z bieżącej lokalizacji. Algorytm następnie cofa się wzdłuż wcześniej odwiedzonych wierzchołków, aż znajdzie wierzchołek połączony z jeszcze bardziej niezbadanym terytorium. Następnie przejdzie nową ścieżką, tak jak poprzednio, wycofując się, gdy napotka ślepe zaułki, i kończąc dopiero wtedy, gdy algorytm cofnie się poza pierwotny wierzchołek „główny” od pierwszego kroku.
DFS jest podstawą wielu algorytmów związanych z grafami, w tym sortowania topologicznego i testowania płaskości .
Pseudo kod
- Wejście : Wykres G i wierzchołek V o G .
- Dane wyjściowe : Etykietowanie krawędzi w połączonym komponencie v jako krawędzie wykrywania i krawędzie tylne.
procedure DFS(G, v) is
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call DFS(G, w)
else
label e as a back edge
Wyszukiwanie wszerz
Przeszukiwanie wszerz (BFS) to kolejna technika przechodzenia przez skończony graf. BFS odwiedza wierzchołki rodzeństwa przed odwiedzeniem wierzchołków podrzędnych, a kolejka jest używana w procesie wyszukiwania. Ten algorytm jest często używany do znalezienia najkrótszej ścieżki z jednego wierzchołka do drugiego.
Pseudo kod
- Wejście : Wykres G i wierzchołek V o G .
- Dane wyjściowe : wierzchołek najbliższy v spełniający pewne warunki lub null, jeśli taki wierzchołek nie istnieje.
procedure BFS(G, v) is
create a queue Q
enqueue v onto Q
mark v
while Q is not empty do
w ← Q.dequeue()
if w is what we are looking for then
return w
for all edges e in G.adjacentEdges(w) do
x ← G.adjacentVertex(w, e)
if x is not marked then
mark x
enqueue x onto Q
return null
Aplikacje
Przeszukiwanie wszerz może być wykorzystane do rozwiązania wielu problemów w teorii grafów, na przykład:
- znajdowanie wszystkich wierzchołków w jednym połączonym komponencie ;
- algorytm Cheneya ;
- znalezienie najkrótszej ścieżki między dwoma wierzchołkami;
- testowanie grafu pod kątem dwudzielności ;
- Numeracja siatek algorytmu Cuthill-McKee ;
- algorytm Forda-Fulkersona do obliczania maksymalnego przepływu w sieci przepływowej ;
- serializacja/deserializacja drzewa binarnego a serializacja w kolejności posortowanej (pozwala na odtworzenie drzewa w wydajny sposób);
- algorytmy generowania labiryntów ;
- algorytm wypełniania zalewania do oznaczania sąsiednich obszarów dwuwymiarowego obrazu lub tablicy n-wymiarowej;
- analiza sieci i relacji.
Eksploracja wykresu
Problem eksploracji grafów można postrzegać jako wariant przechodzenia przez grafy. Jest to problem online , co oznacza, że informacje o wykresie są ujawniane tylko w czasie działania algorytmu. Typowy model jest następujący: mając połączony graf G = ( V , E ) z nieujemnymi wagami krawędzi. Algorytm zaczyna się od pewnego wierzchołka i zna wszystkie wychodzące krawędzie incydentu oraz wierzchołki na końcu tych krawędzi — ale nie więcej. Kiedy odwiedzany jest nowy wierzchołek, ponownie znane są wszystkie wychodzące krawędzie incydentu i wierzchołki na końcu. Celem jest odwiedzenie wszystkich n wierzchołków i powrót do początkowego wierzchołka, ale suma wag trasy powinna być jak najmniejsza. Problem może być również rozumiany jako specyficzna wersja problemu komiwojażera , w której sprzedawca musi odkrywać wykres w podróży.
W przypadku grafów ogólnych najbardziej znanymi algorytmami zarówno dla grafów nieskierowanych, jak i skierowanych jest prosty algorytm zachłanny :
- W przypadku niekierowanym objazd chciwy jest co najwyżej O (ln n ) -razy dłuższy niż objazd optymalny. Najlepsza dolna granica znana dla dowolnego deterministycznego algorytmu online to 10/3.
- Nieskierowane wykresy masy jednostkowej można badać z konkurencyjnym stosunkiem 2 − ε , który jest już ściśle związany z grafami Kijanki .
- W kierowanym przypadku objazd chciwy jest co najwyżej ( n − 1 ) razy dłuższy niż obchód optymalny. To pasuje do dolnej granicy n − 1 . Analogiczne konkurencyjne dolne ograniczenie Ω ( n ) dotyczy również algorytmów randomizowanych, które znają współrzędne każdego węzła w osadzeniu geometrycznym. Jeśli zamiast odwiedzać wszystkie węzły trzeba znaleźć tylko jeden węzeł „skarbu”, konkurencyjne granice wynoszą Θ ( n 2 ) na grafach ukierunkowanych na wagę jednostkową, zarówno dla algorytmów deterministycznych, jak i randomizowanych.
Uniwersalne sekwencje przechodzenia
Uniwersalny sekwencja translacji jest sekwencja instrukcji zawierających przechodzenie wykres dla każdej zwykłej wykresie o określoną liczbę wierzchołków, zaś dla każdego wierzchołka wyjściowego. Dowód probabilistyczny wykorzystali Aleliunas i in. aby pokazać, że istnieje uniwersalna sekwencja przechodzenia z liczbą instrukcji proporcjonalną do O ( n 5 ) dla dowolnego regularnego grafu z n wierzchołkami. Kroki określone w sekwencji są względne do bieżącego węzła, a nie bezwzględne. Na przykład, jeśli bieżący węzeł to v j , a v j ma d sąsiadów, to sekwencja przechodzenia określi następny węzeł do odwiedzenia, v j +1 , jako i- ty sąsiad v j , gdzie 1 ≤ i ≤ d .