Przeszukiwanie grafów

https://en.wikipedia.org/wiki/Graph_traversal

WPROWADZENIE

Wiele własności grafów można poznać, sprawdzając systematycznie każdy jego wierzchołek i każdą jego krawędź. Rozważymy różne sposoby przeszukiwania grafów.

PRZESZUKIWANIE W GŁĄB

Rozważmy następujący problem: chcemy odwiedzić wszystkie wierzchołki grafu po to, aby wykonać na każdym jakąś operację. Funkcja traverse_dfs() realizuje przechodzenie w głąb przez graf (depth-first search, DFS) i ma strukturę rekurencyjną. Zaczynamy od dowolnego węzła start, odwiedzamy go, a następnie rekurencyjnie odwiedzamy każdy nieodwiedzony węzeł dołączony do węzła start. Odwiedzimy na pewno wszystkie węzły, jeżeli graf jest nieskierowany i spójny.

Zbiór krawędzi, które przejdziemy metodą przechodzenia w głąb, tworzy drzewo rozpinające grafu.

def visit(node):     # pewna operacja na wierzchołku
    print("odwiedzamy {}".format(node))

def traverse_dfs(graph, start, visit, visited=None):
    # Przy pierwszym wywołaniu funkcji traverse_dfs
    # tworzymy pustą listę węzłów odwiedzonych.
    if visited is None:
        visited = []   # lepiej set()
    # Odwiedzamy wszystkie węzły dołączone do węzła start.
    visit(start)
    visited.append(start)
    for node in graph[start]:
        if node not in visited:   # wyszukiwanie
            traverse_dfs(graph, node, visit, visited)

Jeżeli graf jest drzewem, rekurencyjne przeszukiwanie grafu w głąb zaczynające się od korzenia jest równoważne przechodzeniu przez drzewo w porządku preorder.

W reprezentacji list sąsiedztwa czas przeszukiwania grafu w głąb jest O(V+E).

Zamiast korzystania z rekurencji możemy określić metodę przechodzenia przez graf używającą jawnego stosu, podobnie jak przy przechodzeniu przez drzewo binarne metodą preorder.

def traverse_stack(graph, start, visit):
    # Przechodzenie w głąb z jawnym stosem.
    stack = []   # lista jako stos
    visited = []   # lepiej set()
    stack.append(start)
    while stack:
        start = stack.pop()
        if start not in visited:   # wyszukiwanie
            visit(start)
            visited.append(start)
            for node in graph[start]:
                if node not in visited:
                    stack.append(node)

Podejście ze stosem ma tę wadę, że na stosie może się znaleźć kilka elementów odpowiadającym temu samemu węzłowi. Dzieje się tak nawet wtedy, gdy przed umieszczeniem węzła na stosie sprawdzamy, czy został już odwiedzony. Rozwiązaniem jest implementacja stosu, która uniemożliwia umieszczanie na stosie dwóch takich samych elementów przez zastosowanie reguły zastępowania starego elementu nowym. Wtedy wielkość stosu można ograniczyć do liczby wierzchołków V.

Należy zwrócić uwagę, że kolejność odwiedzania wierzchołków w podejściu rekurencyjnym i podejściu ze stosem na ogół jest różna. Różnica wynika z kolejności pobierania elementów z listy sąsiedztwa.

# Wersja wyznaczająca drzewo DFS w postaci słownika.

def traverse_dfs(graph, source, parent=None, pre_action=None, post_action=None):
    if parent is None:
        parent = {source: None}
    if pre_action:
        pre_action(source)
    for target in graph[source]:
        if target not in parent:   # wyszukiwanie O(1)
            parent[target] = source
            traverse_dfs(graph, target, parent, pre_action, post_action)
    if post_action:
        post_action(source)
    return parent

# Wyznaczenie kolejności odwiedzanych i przetworzonych wierzchołków.
preorder = []
postorder = []
parent = traverse_dfs(graph, source,
    pre_action=lambda node: preorder.append(node),
    post_action=lambda node: postorder.append(node))

PRZESZUKIWANIE WSZERZ

Funkcja traverse_bfs() realizuje przechodzenie wszerz (breadth-first search, BFS) i wykorzystuje kolejkę do przechowywania wierzchołków. Algorytm przechodzi przez graf we wszystkich kierunkach. Przed przejściem z danego węzła do kolejnego odwiedza wszystkie połączone z nim węzły.

import collections

def traverse_bfs(graph, start, visit):
    queue = collections.deque()   # deque jako kolejka
    visited = []   # lepiej set()
    queue.append(start)
    while queue:
        start = queue.popleft()
        if start not in visited:   # wyszukiwanie
            visit(start)
            visited.append(start)
            for node in graph[start]:
                if node not in visited:
                    queue.append(node)

W tym podejściu w kolejce również może się znaleźć kilka elementów odpowiadającym temu samemu węzłowi. Rozwiązaniem jest stosowanie reguły pomijania nowego powtarzającego się elementu. Wtedy wielkość kolejki można ograniczyć do liczby wierzchołków V.

# Wersja wyznaczająca drzewo BFS w postaci słownika.

import collections

def traverse_bfs(graph, source, pre_action=None, post_action=None):
    parent = {source: None}
    queue = collections.deque()
    queue.append(source)
    if pre_action:
        pre_action(source)
    while queue:
        source = queue.popleft()
        for target in graph[source]:
            if target not in parent:   # wyszukiwanie O(1)
                parent[target] = source
                queue.append(target)
                if pre_action:
                    pre_action(target)
        if post_action:
            post_action(source)
    return parent

# Wyznaczenie kolejności odwiedzanych wierzchołków.
order = []
parent = traverse_bfs(graph, source,
    pre_action=lambda node: order.append(node))