Vzory Pythonu – Implementace grafů | Python.org

Poznámky ke změnám: 2/22/98, 3/2/98, 12/4/00: Tato verze této eseje opravuje několik chyb v kódu. 6/10/19: Staženífind_shortest_pathjako „téměř optimální“. 8/11/19: Oprava náhodného použitífind_graph()místofind_path()

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

Grafy jsou sítě složené z uzlů spojených hranami nebo oblouky. V neorientovaných grafech mají spojení mezi uzly směr a nazývají se oblouky; v neorientovaných grafech nemají spojení žádný směr a nazývají se hrany. Probíráme především směrové grafy. Algoritmy v grafech zahrnují hledání cesty mezi dvěma uzly, hledání nejkratší cesty mezi dvěma uzly, určování cyklů v grafu (cyklus je neprázdná cesta z uzlu do sebe sama), hledání cesty, která dosáhne všech uzlů (známý „problém obchodního cestujícího“), a tak dále. Někdy jsou s uzly nebo oblouky grafu spojeny váhy nebo náklady a nás zajímá nalezení nejlevnější cesty.

Existuje rozsáhlá literatura o grafových algoritmech, které jsou důležitou součástí diskrétní matematiky. Grafy mají také velké praktické využití vpočítačových algoritmech. Zjevné příklady lze najít ve správěsítí, ale příkladů je mnoho i v mnoha dalších oblastech. Například vztahy volajícího a volaného v počítačovém programu lze vidět jako graf (kde cykly označují rekurzi a nedosažitelné uzly představují mrtvý kód).

Málo programovacích jazyků poskytuje přímou podporu grafů jako datového typu a Python není výjimkou. Grafy se však snadno vytvářejí ze seznamůa slovníků. Například zde je jednoduchý graf (v těchto sloupcích nemohu použít výkresy, takže vypíšu oblouky grafu):

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

Tento graf má šest uzlů (A-F) a osm oblouků. Lze jej reprezentovat pomocí následující datové struktury jazyka Python:

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

Jedná se o slovník, jehož klíče jsou uzly grafu. Pro každý klíč je odpovídající hodnotou seznam obsahující uzly, které jsou spojeny přímým obloukem z tohoto uzlu. To je asi tak jednoduché, jak to jen jde (ještě jednodušší by bylo reprezentovat uzly čísly místo jmény, ale jména jsou pohodlnější a lze je snadno upravit tak, aby nesla více informací, například názvy měst).

Napíšeme jednoduchou funkci pro určení cesty mezi dvěma uzly. Jako argumenty přijme graf a počáteční a koncový uzel. Vrátí seznam uzlů (včetně počátečních a koncových uzlů), které tvoří cestu.Pokud se nepodaří najít žádnou cestu, vrátí None. Stejný uzel se na vrácené cestě nebude vyskytovat více než jednou (tj. nebude obsahovat cykly). Algoritmus používá důležitou techniku zvanou backtracking: zkouší postupně každou možnost, dokud nenajde řešení.

 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

Ukázka běhu (s použitím výše uvedeného grafu):

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

Druhý příkaz ‚if‘ je nutný pouze v případě, že existují uzly, které jsou uvedeny jako koncové body oblouků, ale které samy nemají vycházející oblouky a nejsou v grafu vůbec uvedeny. Takové uzly by také mohly být obsaženy v grafu s prázdným seznamem vycházejících oblouků, ale někdy je vhodnější to nevyžadovat.

Všimněte si, že zatímco uživatel volá find_path() se třemi argumenty,sám se volá se čtvrtým argumentem: cestou, která již byla projita.Výchozí hodnota tohoto argumentu je prázdný seznam, “, což znamená, že dosud nebyly projity žádné uzly. Tento argument se používá, aby se zabránilo cyklům (první ‚if‘ uvnitř cyklu ‚for‘). Argument ‚path‘ se nemění:přiřazení „path = path + “ vytvoří nový seznam. Kdybychom místo toho napsali „path.append(start)“, modifikovali bychom proměnnou’path‘ ve volajícím, což by mělo katastrofální následky. (Při použití tuplů bychom si mohli být jisti, že k tomu nedojde, ovšem za cenu toho, že bychom museli napsat „path = path + (start,)“, protože „(start)“ není singletonový tupl – je to jen výraz v závorce.)

Jednoduše lze tuto funkci změnit tak, aby místo první nalezené cesty vracela seznam všech cest (bez cyklů):

 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

Ukázkový běh:

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

Jiná varianta najde nejkratší cestu:

 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

Ukázkový běh:

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

Tyto funkce jsou asi tak jednoduché, jak jen mohou být. Přesto jsou téměřoptimální (pro kód napsaný v jazyce Python). V dalším sloupku o vzorech Pythonu se pokusím analyzovat rychlost jejich běhu a zlepšit jejich výkonnost za cenu většího množství kódu.

DOPLNĚNÍ: Eryk Kopczyński upozornil, že tyto funkce nejsou optimální. Naopak, „tento program běží v exponenciálním čase,zatímco find_shortest_path lze provést v lineárním čase pomocí BFS . Navíc lineární BFS je jednodušší:“

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

Všimněte si, že vrací cestu v podivném formátu, např., 'B'], 'D']. Konkrétnělen(find_shortest_path(graph, 'A', 'D'))dá nesprávnou odpověď (2, protože vnější seznam má délku 2). Je to proto, že připojení se provádí jako, next]namístodist+. Druhý způsob by spotřebovalčtyřnásobek času a paměti, ale stále by měl být v pořádku pro relativně malé grafy;jinak je snadné seznam převést do správného formátu.

Další variantou by bylo přidat více datové abstrakce: vytvořit třídu pro reprezentaci grafů, jejíž metody implementují různé algoritmy. To sice apeluje na touhu po strukturovaném programování, ale nezvyšuje to efektivitu kódu (spíše naopak). Usnadňuje však přidávánírůzných značek k uzlům nebo obloukům a přidávání algoritmů, které tyto značky zohledňují (např. hledání nejkratší cesty mezi dvěma městy na mapě). I to bude předmětem dalšího sloupku.