Warnung
Diese Seite bleibt aus historischen Gründen hier und kann veraltete oder falsche Informationen enthalten.
Änderungshinweise: 22.2.98, 2.3.98, 4.12.00: Diese Version dieses Aufsatzes behebt mehrere Fehler im Code. 6/10/19: Rücknahme vonfind_shortest_pathals „nahezu optimal“. 8/11/19: Korrektur der versehentlichen Verwendung vonfind_graph()anstelle vonfind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
Graphen sind Netzwerke, die aus Knoten bestehen, die durch Kanten oder Bögen verbunden sind. In gerichteten Graphen haben die Verbindungen zwischen den Knoten eine Richtung und werden Bögen genannt; in ungerichteten Graphen haben die Verbindungen keine Richtung und werden Kanten genannt. Wir behandeln hauptsächlich gerichtete Graphen. Algorithmen in Graphen umfassen die Suche nach einem Pfad zwischen zwei Knoten, die Suche nach dem kürzesten Pfad zwischen zwei Knoten, die Bestimmung von Zyklen im Graphen (ein Zyklus ist ein nicht leerer Pfad von einem Knoten zu sich selbst), die Suche nach einem Pfad, der alle Knoten erreicht (das berühmte „Travelling-Salesman-Problem“), und so weiter. Manchmal sind die Knoten oder Bögen eines Graphen mit Gewichten oder Kosten verbunden, und wir sind daran interessiert, den billigsten Weg zu finden.
Es gibt eine umfangreiche Literatur über Graphenalgorithmen, die einen wichtigen Teil der diskreten Mathematik darstellen. Graphen haben auch einen großen praktischen Nutzen in Computeralgorithmen. Offensichtliche Beispiele finden sich bei der Verwaltung von Netzwerken, aber auch in vielen anderen Bereichen gibt es zahlreiche Beispiele. So lassen sich beispielsweise die Beziehungen zwischen Aufrufer und Abrufer in einem Computerprogramm als Graph darstellen (wobei Zyklen eine 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. Allerdings lassen sich Graphen leicht aus Listen und Wörterbüchern erstellen. Hier ist zum Beispiel ein einfacher Graph (ich kann in diesen Spalten keine Zeichnungen 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
Dieser Graph hat sechs Knoten (A-F) und acht Bögen. Er kann durch die folgende Python-Datenstruktur dargestellt werden:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Dies ist ein Wörterbuch, dessen Schlüssel die Knoten des Graphen sind. Für jeden Schlüssel ist der entsprechende Wert eine Liste mit den Knoten, die durch einen direkten Bogen mit diesem Knoten verbunden sind. Das ist so einfach wie möglich (noch einfacher wäre es, die Knoten durch Zahlen statt durch Namen darzustellen, aber Namen sind bequemer und können leicht mit weiteren Informationen versehen werden, z. B. mit Städtenamen).
Schreiben wir eine einfache Funktion, um einen Pfad zwischen zwei Knoten zu bestimmen. Sie nimmt einen Graphen und die Start- und Endknoten als Argumente. Sie gibt eine Liste von Knoten (einschließlich des Start- und des Endknotens) zurück, die den Pfad bilden.Wenn kein Pfad gefunden werden kann, gibt sie None zurück. Der gleiche Knoten wird nicht mehr als einmal auf dem zurückgegebenen Pfad vorkommen (d.h. er wird keine Zyklen enthalten). Der Algorithmus verwendet eine wichtige Technik, die Backtracking genannt wird: Er probiert jede Möglichkeit der Reihe nach aus, bis er eine Lösung findet.
def find_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None for node in graph: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None
Ein Beispiellauf (unter Verwendung des obigen Graphen):
>>> find_path(graph, 'A', 'D') >>>
Die zweite ‚if‘-Anweisung ist nur für den Fall notwendig, dass es Knoten gibt, die als Endpunkte für Bögen aufgelistet sind, die aber selbst keine ausgehenden Bögen haben und überhaupt nicht im Graphen aufgeführt sind. Solche Knoten könnten auch im Graphen enthalten sein, mit einer leeren Liste von ausgehenden Bögen, aber manchmal ist es bequemer, dies nicht zu verlangen.
Beachten Sie, dass, während der Benutzer find_path() mit drei Argumenten aufruft, es sich selbst mit einem vierten Argument aufruft: der Pfad, der bereits durchlaufen wurde.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 Argument „path“ wird nicht geändert: Die Zuweisung „path = path + “ erzeugt eine neue Liste. Hätten wir stattdessen „path.append(start)“ geschrieben, hätten wir die Variable „path“ im Aufrufer verändert, mit katastrophalen Folgen. (Bei der Verwendung von Tupeln hätten wir sicher sein können, dass dies nicht passieren würde, allerdings um den Preis, dass wir „path = path + (start,)“ schreiben müssten, da „(start)“ kein Singleton-Tupel ist – es ist nur ein Ausdruck in Klammern.)
Es ist einfach, diese Funktion so zu ändern, dass sie eine Liste aller Pfade (ohne Zyklen) anstelle des ersten gefundenen Pfades zurückgibt:
def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
Ein Beispieldurchlauf:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Eine andere Variante findet den kürzesten Pfad:
def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: 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
Beispieldurchlauf:
>>> find_shortest_path(graph, 'A', 'D') >>>
Diese Funktionen sind so einfach, wie sie nur sein können. Dennoch sind sie nahezu optimal (für in Python geschriebenen Code). In einer weiteren Kolumne über Python-Patterns werde ich versuchen, ihre Ausführungsgeschwindigkeit zu analysieren und ihre Leistung zu verbessern, was allerdings mit mehr Code verbunden ist.
UPDATE: Eryk Kopczyński hat darauf hingewiesen, dass diese Funktionen nicht optimal sind. Im Gegenteil, „dieses Programm läuft in exponentieller Zeit, während find_shortest_path in linearer Zeit mit BFS durchgeführt werden kann. Außerdem ist ein lineares BFS einfacher:“
# Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)
Beachte, dass dies den Pfad in einem seltsamen Format zurückgibt, z.B., 'B'], 'D']. Insbesondere,len(find_shortest_path(graph, 'A', 'D'))liefert die falsche Antwort (2, weil die äußere Liste die Länge 2 hat). Das liegt daran, dass das Anhängen als, next]und nicht alsdist+erfolgt. Die zweite Methode würde quadratische Zeit und Speicher verbrauchen, sollte aber dennoch für relativ kleine Graphen ausreichen; ansonsten ist es einfach, die Liste in das richtige Format zu bringen.
Eine andere Variante wäre, mehr Datenabstraktion hinzuzufügen: eine Klasse zur Darstellung von Graphen zu erstellen, deren Methoden die verschiedenen Algorithmen implementieren. Dies kommt zwar dem Wunsch nach strukturierter Programmierung entgegen, macht den Code aber nicht effizienter (im Gegenteil). Es erleichtert jedoch das Hinzufügen verschiedener Etiketten zu den Knoten oder Bögen und das Hinzufügen von Algorithmen, die diese Etiketten berücksichtigen (z. B. um den kürzesten Weg zwischen zwei Städten auf einer Karte zu finden). Auch dies wird Thema einer weiteren Kolumne sein.