Python Patterns – Implementering af grafer | Python.org

Ændringsbemærkninger: 22/2/98, 3/2/98, 4/12/00: Denne version af dette essay retter flere fejl i koden. 6/10/19: Tilbagetrækning affind_shortest_pathsom “næsten optimal”. 8/11/19: Retter utilsigtet brug affind_graph()i stedet forfind_path()

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

Grafer er netværk bestående af knuder, der er forbundet af kanter eller buer. I indirekte grafer har forbindelserne mellem knuder en retning og kaldes buer; i udirigerede grafer har forbindelserne ingen retning og kaldes kanter. Vi diskuterer hovedsageligt dirigerede grafer. Algoritmer i grafer omfatter bl.a. at finde en vej mellem to knudepunkter, at finde den korteste vej mellem to knudepunkter, at bestemme cyklusser i grafen (en cyklus er en ikke-tom vej fra et knudepunkt til sig selv), at finde en vej, der når alle knudepunkter (det berømte “traveling salesman problem”) osv. Nogle gange er knuderne eller buerne i en graf forbundet med vægte eller omkostninger, og vi er interesseret i at finde den billigste vej.

Der findes en omfattende litteratur om grafalgoritmer, som er en vigtig del af den diskrete matematik. Grafer har også stor praktisk anvendelse i computeralgoritmer. Der findes indlysende eksempler i forbindelse med forvaltning af net, men der findes masser af eksempler på mange andre områder. F.eks. kan forbindelserne mellem en kalder og en kalder i et computerprogram ses som en graf (hvor cyklusser angiver rekursion, og uopnåelige knuder repræsenterer død kode).

Få programmeringssprog giver direkte støtte til grafer som datatype, og Python er ingen undtagelse. Grafer kan dog let opbygges ud fra listerog ordbøger. Her er f.eks. en simpel graf (jeg kan ikke bruge tegninger i disse kolonner, så jeg skriver grafens buer ned):

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

Denne graf har seks knuder (A-F) og otte buer. Den kan repræsenteres ved følgende Python-datastruktur:

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

Dette er en ordbog, hvis nøgler er noderne i grafen. For hver nøgle er den tilsvarende værdi en liste, der indeholder de knuder, der er forbundet med en direkte bue fra dette knudepunkt. Dette er så simpelt som det kan blive (endnu mere simpelt kunne knuderne repræsenteres ved tal i stedet for navne, men navne er mere praktisk og kan let gøres til at bære flere oplysninger, f.eks. bynavne).

Lad os skrive en simpel funktion til at bestemme en sti mellem to knuder. Denmodtager en graf og start- og slutknuderne som argumenter. Den returnerer en liste over knuder (herunder start- og slutknuderne), der udgør stien.Hvis der ikke kan findes nogen sti, returnerer den None. Den samme knude vil ikke forekomme mere end én gang på den returnerede sti (dvs. den vil ikke indeholde cyklusser). Algoritmen anvender en vigtig teknik kaldet backtracking: den prøver hver mulighed efter tur, indtil den finder en løsning.

 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

En prøvekørsel (ved hjælp af grafen ovenfor):

 >>> find_path(graph, 'A', 'D') >>>

Den anden “if”-erklæring er kun nødvendig, hvis der er knuder, der er opført som slutpunkter for buer, men som ikke selv har udgående buer, og som slet ikke er opført i grafen. Sådanne knuder kunne også være indeholdt i grafen med en tom liste over udgående buer, men nogle gange er det mere praktisk ikke at kræve dette.

Bemærk, at mens brugeren kalder find_path() med tre argumenter, kalder den sig selv med et fjerde argument: den sti, der allerede er blevet gennemløbet.Standardværdien for dette argument er den tomme liste, ”, hvilket betyder, at der endnu ikke er blevet gennemløbet nogen knuder. Dette argument bruges til at undgå cyklusser (den første “if” i “for”-sløjfen). Argumentet ‘path’ ændres ikke: tilknytningen “path = path + ” skaber en ny liste. Hvis vi i stedet havde skrevet “path.append(start)”, ville vi have ændret variablen “path” i opkalderen, hvilket ville have haft katastrofale følger. (Ved at bruge tupler kunne vi have været sikre på, at dette ikke ville ske, på bekostning af at skulle skrive “path = path + (start,)”, da “(start)” ikke er en singleton-tupel – det er blot et udtryk i parentes.)

Det er nemt at ændre denne funktion til at returnere en liste over alle stier (uden cykler) i stedet for den første sti, den finder:

 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

Eksempelkørsel:

 >>> find_all_paths(graph, 'A', 'D') , , ] >>>

En anden variant finder den korteste sti:

 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

Eksempelkørsel:

 >>> find_shortest_path(graph, 'A', 'D') >>>

Disse funktioner er omtrent så enkle som de kan blive. Alligevel er de næsten optimale (for kode skrevet i Python). I en anden Python Pattern-klumme vil jeg forsøge at analysere deres løbehastighed og forbedre deres ydeevne, på bekostning af mere kode.

OPDATE: Eryk Kopczyński gjorde opmærksom på, at disse funktioner ikke er optimale. Tværtimod, “dette program kører i eksponentiel tid,mens find_shortest_path kan udføres i lineær tid ved hjælp af BFS . Desuden er en lineær BFS mere enkel:”

 # 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)

Bemærk, at dette returnerer stien i et mærkeligt format, f.eks., 'B'], 'D']. Især villen(find_shortest_path(graph, 'A', 'D'))give det forkerte svar (2, fordi den ydre liste har en længde på 2). Dette skyldes, at append udføres som, next]i stedet fordist+. Den anden metode ville bruge kvadratisk tid og hukommelse, men burde stadig være fin for relativt små grafer; ellers er det let at omdanne listen til det korrekte format.

En anden variation ville være at tilføje mere dataabstraktion: opret en klasse til at repræsentere grafer, hvis metoder implementerer de forskellige algoritmer. Selv om dette tilgodeser ønsket om struktureret programmering, gør det ikke koden mere effektiv (tværtimod). Det gør det dog lettere at tilføje forskellige etiketter til knuder eller buer og at tilføje algoritmer, der tager hensyn til disse etiketter (f.eks. for at finde den korteste vej mellem to byer på et kort). Dette vil også blive genstand for en anden klumme.