Deze pagina blijft hier om historische redenen en het kan verouderde of onjuiste informatie bevatten.
Notities over wijzigingen: 2/22/98, 3/2/98, 12/4/00: Deze versie van dit essay verhelpt verschillende bugs in de code. 6/10/19: Intrekking vanfind_shortest_pathals “bijna optimaal”. 8/11/19: Herstel per ongeluk gebruik vanfind_graph()in plaats vanfind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
Grafieken zijn netwerken die bestaan uit knooppunten verbonden door randen of bogen. In indirecte grafieken hebben de verbindingen tussen knooppunten een richting en worden ze bogen genoemd; in niet-gerichte grafieken hebben de verbindingen geen richting en worden ze randen genoemd. Wij bespreken hoofdzakelijk gerichte grafieken. Algoritmen voor grafieken zijn onder andere het vinden van een pad tussen twee knooppunten, het vinden van het kortste pad tussen twee knooppunten, het bepalen van cycli in de grafiek (een cyclus is een niet-leeg pad van een knooppunt naar zichzelf), het vinden van een pad dat alle knooppunten bereikt (het beroemde “handelsreizigersprobleem”), enzovoort. Soms zijn aan de knooppunten of bogen van een grafiek gewichten of kosten verbonden, en zijn we geïnteresseerd in het vinden van het goedkoopste pad.
Er is veel literatuur over grafiekalgoritmen, die een belangrijk onderdeel vormen van de discrete wiskunde. Grafieken worden ook veel gebruikt in computeralgoritmen. Duidelijke voorbeelden zijn te vinden in het beheer van netwerken, maar er zijn voorbeelden in overvloed op vele andere gebieden. Bijvoorbeeld, caller-callee relaties in een computer programma kan worden gezien als een grafiek (waar cycli geven recursie, en onbereikbare knooppunten vertegenwoordigen deadcode).
Weinig programmeertalen bieden directe ondersteuning voor grafieken als een datatype, en Python is geen uitzondering. Grafieken zijn echter gemakkelijk op te bouwen uit lijsten en woordenboeken. Hier is bijvoorbeeld een eenvoudige grafiek (ik kan geen tekeningen gebruiken in deze kolommen, dus schrijf ik de bogen van de grafiek op):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Deze grafiek heeft zes knopen (A-F) en acht bogen. Zij kan worden voorgesteld door de volgende Python-gegevensstructuur:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Dit is een woordenboek waarvan de sleutels de knopen van de grafiek zijn. Voor elke sleutel is de corresponderende waarde een lijst met de knooppunten die verbonden zijn door een directe boog vanaf dit knooppunt. Eenvoudiger kan het niet (de knooppunten zouden ook met getallen kunnen worden weergegeven in plaats van namen, maar namen zijn handiger en kunnen gemakkelijk meer informatie bevatten, zoals plaatsnamen).
Laten we eens een eenvoudige functie schrijven om een pad tussen twee knooppunten te bepalen. De functie neemt een grafiek en de begin- en eindknopen als argumenten. De functie geeft een lijst van knooppunten terug (inclusief de begin- en eindknooppunten) die het pad vormen. Als er geen pad kan worden gevonden, geeft de functie Geen terug. Hetzelfde knooppunt komt niet meer dan één keer voor op het geretourneerde pad (d.w.z. het bevat geen cycli). Het algoritme gebruikt een belangrijke techniek die backtracking heet: het probeert elke mogelijkheid om de beurt totdat het een oplossing vindt.
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
Een voorbeeldrun (met de bovenstaande grafiek):
>>> find_path(graph, 'A', 'D') >>>
De tweede ‘if’-opdracht is alleen nodig voor het geval er knooppunten zijn die als eindpunt van bogen in de lijst staan, maar zelf geen uitgaande bogen hebben, en dus helemaal niet in de grafiek staan. Zulke knooppunten zouden ook in de grafiek kunnen worden opgenomen, met een lege lijst van uitgaande bogen, maar soms is het handiger om dit niet te vereisen.
Merk op dat terwijl de gebruiker find_path() aanroept met drie argumenten, het zichzelf aanroept met een vierde argument: het pad dat al doorlopen is.De standaardwaarde voor dit argument is de lege lijst, ”, wat betekent dat er nog geen knooppunten doorlopen zijn. Dit argument wordt gebruikt om cycli te vermijden (de eerste ‘if’ in de ‘for’-lus). Het argument “path” wordt niet gewijzigd: de opdracht “path = path + ” creëert een nieuwe lijst. Als we in plaats daarvan “path.append(start)” hadden geschreven, zouden we de variabele “path” in de aanroeper hebben gewijzigd, met desastreuze gevolgen. (Als we tupels hadden gebruikt, hadden we er zeker van kunnen zijn dat dit niet zou gebeuren, maar dan hadden we wel moeten schrijven “path = path + (start,)” omdat “(start)” geen singleton tuple is — het is gewoon een expressie tussen haakjes.)
Het is eenvoudig om deze functie zo te veranderen dat ze een lijst van alle paden (zonder cycli) teruggeeft in plaats van het eerste pad dat ze vindt:
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
Een voorbeeldrun:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Een andere variant vindt het kortste pad:
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
Een voorbeeldrun:
>>> find_shortest_path(graph, 'A', 'D') >>>
Deze functies zijn zo eenvoudig als maar kan. Toch zijn ze bijna optimaal (voor code geschreven in Python). In een volgende Python Pattern column zal ik proberen hun loopsnelheid te analyseren en hun prestaties te verbeteren, ten koste van meer code.
UPDATE: Eryk Kopczyński wees erop dat deze functies niet optimaal zijn. Integendeel, “dit programma loopt in exponentiële tijd, terwijl find_shortest_path kan worden gedaan in lineaire tijd met behulp van BFS . Bovendien is een lineaire BFS eenvoudiger:”
# 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)
Merk op dat dit het pad in een vreemd formaat teruggeeft, b.v.,, 'B'], 'D']. In het bijzonder zallen(find_shortest_path(graph, 'A', 'D'))het onjuiste antwoord geven (2, omdat de buitenste lijst lengte 2 heeft). Dit komt omdat append wordt gedaan als, next]in plaats vandist+. De tweede methode zou kwadratische tijd en geheugen gebruiken, maar zou nog steeds goed moeten zijn voor relatief kleine grafieken; anders is het eenvoudig om de lijst in het juiste formaat om te zetten.
Een andere variatie zou zijn om meer data-abstractie toe te voegen: maak een klasse voor het voorstellen van grafieken, waarvan de methoden de verschillende algoritmen implementeren. Hoewel dit appelleert aan het verlangen naar gestructureerd programmeren, maakt het de code niet efficiënter (integendeel). Het wordt wel gemakkelijker om verschillende labels toe te voegen aan knopen of bogen en om algoritmen toe te voegen die rekening houden met die labels (bv. om de kortste route te vinden tussen twee steden op een kaart). Ook dit zal het onderwerp zijn van een volgende column.