Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.
All rights reserved.
Licensed under the PSF license.

Es gibt beträchtliche Literatur über Graphenalgorithmen, die ein wichtiger Bestandteil der diskreten Mathematik sind. Graphen haben auch praktische Anwendung in vielen Computer-Algorithmen. Offensichtliche Beispiele finden sich in der Verwaltung von Netzwerken, aber Beispiele gibt es in vielen anderen Bereichen. Zum Beispiel können Aufrufer-Aufrufsempfänger-Beziehungen in einem Computerprogramm als Graph betrachtet werden (wobei Zyklen Rekursion anzeigen und unerreichbare Knoten toten Code darstellen).

Nur wenige Programmiersprachen bieten direkte Unterstützung für Graphen als Datentyp, und Python ist keine Ausnahme. Graphen lassen sich jedoch leicht aus Listen und Wörterbüchern aufbauen. Hier ist zum Beispiel ein einfacher Graph (ich kann keine Zeichnungen in diesen Spalten verwenden, also schreibe ich die Bögen des Graphen auf)

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    graph = {'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']}

Schreiben wir eine einfache Funktion, um einen Pfad zwischen zwei Knoten zu ermitteln. Sie nimmt einen Graphen sowie den Start- und Endknoten als Argumente. Sie gibt eine Liste von Knoten (einschließlich Start- und Endknoten) zurück, die den Pfad bilden. Wenn kein Pfad gefunden werden kann, gibt sie None zurück. Derselbe Knoten wird nicht mehr als einmal im zurückgegebenen Pfad vorkommen (d.h. er enthält keine Zyklen). Der Algorithmus verwendet eine wichtige Technik namens Backtracking: Er versucht jede Möglichkeit der Reihe nach, bis er eine Lösung findet.

    def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None

    >>> find_path(graph, 'A', 'D')
    ['A', 'B', 'C', 'D']
    >>>

Beachten Sie, dass find_path(), obwohl der Benutzer es mit drei Argumenten aufruft, sich selbst mit einem vierten Argument aufruft: dem bereits durchlaufenen Pfad. Der Standardwert für dieses Argument ist die leere Liste '[]', was bedeutet, dass noch keine Knoten durchlaufen wurden. Dieses Argument wird verwendet, um Zyklen zu vermeiden (das erste 'if' innerhalb der 'for'-Schleife). Das 'path'-Argument wird nicht verändert: die Zuweisung "path = path + [start]" erstellt eine neue Liste. Hätten wir stattdessen "path.append(start)" geschrieben, hätten wir die Variable 'path' im Aufrufer verändert, mit desaströsen Folgen. (Unter Verwendung von Tupeln hätten wir sicherstellen können, dass dies nicht passiert, auf Kosten der Notwendigkeit, "path = path + (start,)" zu schreiben, da "(start)" kein Singleton-Tupel ist – es ist nur ein in Klammern gesetzter Ausdruck.)

Es ist einfach, diese Funktion zu ändern, um anstelle des ersten gefundenen Pfades eine Liste aller Pfade (ohne Zyklen) zurückzugeben

    def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

    >>> find_all_paths(graph, 'A', 'D')
    [['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]
    >>>

    def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        shortest = None
        for node in graph[start]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    >>> find_shortest_path(graph, 'A', 'D')
    ['A', 'C', 'D']
    >>>

UPDATE: Eryk Kopczyński wies darauf hin, dass diese Funktionen nicht optimal sind. Im Gegenteil, "dieses Programm läuft in exponentieller Zeit, während find_shortest_path mit BFS [Breadth First Search] in linearer Zeit erledigt werden kann. Außerdem ist ein lineares BFS einfacher:"

    # Code by Eryk Kopczyński
    def find_shortest_path(graph, start, end):
        dist = {start: [start]}
        q = deque(start)
        while len(q):
            at = q.popleft()
            for next in graph[at]:
                if next not in dist:
                    dist[next] = [dist[at], next]
                    q.append(next)
        return dist.get(end)

Eine weitere Variation wäre, mehr Datenabstraktion hinzuzufügen: eine Klasse zur Darstellung von Graphen erstellen, deren Methoden die verschiedenen Algorithmen implementieren. Das mag dem Wunsch nach strukturiertem Programmieren entgegenkommen, macht den Code aber nicht effizienter (im Gegenteil). Es erleichtert jedoch das Hinzufügen verschiedener Beschriftungen zu den Knoten oder Bögen und das Hinzufügen von Algorithmen, die diese Beschriftungen berücksichtigen (z.B. um die kürzeste Route zwischen zwei Städten auf einer Karte zu finden).Auch dies wird Gegenstand einer weiteren Spalte sein.