Python - algorytmy wykresów

Wykresy są bardzo użytecznymi strukturami danych w rozwiązywaniu wielu ważnych matematycznych wyzwań. Na przykład topologia sieci komputerowej lub analiza struktur molekularnych związków chemicznych. Są również używane w ruchu miejskim lub planowaniu tras, a nawet w ludzkich językach i ich gramatyce. Wszystkie te aplikacje mają wspólne wyzwanie polegające na przechodzeniu przez wykres przy użyciu jego krawędzi i upewnianiu się, że odwiedzane są wszystkie węzły wykresu. Istnieją dwie powszechnie znane metody wykonywania tego przemierzania, które opisano poniżej.

Głębokie pierwsze przejście:

Algorytm ten, zwany także przeszukiwaniem pierwszego głębi (DFS), przechodzi przez wykres w ruchu w kierunku głębi i używa stosu do zapamiętania, aby uzyskać następny wierzchołek, aby rozpocząć wyszukiwanie, gdy ślepy zaułek występuje w dowolnej iteracji. Wdrażamy DFS dla wykresu w Pythonie przy użyciu ustawionych typów danych, ponieważ zapewniają one wymagane funkcje do śledzenia odwiedzanych i nieodwiedzonych węzłów.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

Wykonanie powyższego kodu daje następujący wynik -

a b d e c

Pierwsze przejście szerokości

Algorytm ten, zwany również przeszukiwaniem wszerz (BFS), przechodzi przez ruch oddziału wszerz wykresu i używa kolejki do zapamiętania, aby pobrać następny wierzchołek do rozpoczęcia wyszukiwania, gdy ślepy zaułek występuje w dowolnej iteracji. Proszę odwiedzić ten link w naszej witrynie internetowej, aby zrozumieć szczegóły kroków BFS dla wykresu.

Implementujemy BFS dla wykresu w Pythonie przy użyciu omówionej wcześniej struktury danych kolejki. Kiedy nadal odwiedzamy sąsiednie nieodwiedzone węzły i dodajemy je do kolejki. Następnie zaczynamy usuwać z kolejki tylko ten węzeł, który pozostał bez nieodwiedzonych węzłów. Zatrzymujemy program, gdy nie ma następnego sąsiedniego węzła do odwiedzenia.

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Wykonanie powyższego kodu daje następujący wynik -

a c b d e