Figyelmeztetés
Ez az oldal történelmi okokból marad itt, és elavult vagy helytelen információkat tartalmazhat.
Változtatási megjegyzések: 2/22/98, 3/2/98, 12/4/00: A dolgozat ezen verziója több hibát is kijavít a kódban. 19.10.6.: Afind_shortest_pathvisszavonása, mint “majdnem optimális”. 8/11/19: Afind_graph()véletlen használatának javítása afind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
helyett A gráfok olyan hálózatok, amelyek élekkel vagy ívekkel összekapcsolt csomópontokból állnak. Az irányított gráfokban a csomópontok közötti kapcsolatoknak van irányuk, és íveknek nevezzük őket; az irányítatlan gráfokban a kapcsolatoknak nincs irányuk, és éleknek nevezzük őket. Elsősorban irányított gráfokat tárgyalunk. A gráfok algoritmusai közé tartozik a két csomópont közötti út megtalálása, a legrövidebb út megtalálása két csomópont között, ciklusok meghatározása a gráfban (a ciklus egy nem üres út egy csomópontból önmagához), olyan út megtalálása, amely minden csomópontot elér (a híres “utazó ügynök probléma”) stb. Néha a gráf csomópontjaihoz vagy íveihez súlyok vagy költségek kapcsolódnak, és a legolcsóbb útvonal megtalálása érdekel bennünket.
A gráf algoritmusoknak, amelyek a diszkrét matematika fontos részét képezik, jelentős irodalma van. A gráfoknak sok gyakorlati haszna van a számítógépes algoritmusokban is. Nyilvánvaló példákat találhatunk a hálózatok kezelésében, de számos más területen is találhatunk példákat. Például egy számítógépes programban a hívó és a hívott közötti kapcsolatokat gráfnak tekinthetjük (ahol a ciklusok a rekurziót jelzik, az elérhetetlen csomópontok pedig a holtkódot).
Néhány programozási nyelv nyújt közvetlen támogatást a gráfok adattípusaként, és ez alól a Python sem kivétel. A gráfok azonban könnyen felépíthetők listákbólés szótárakból. Itt van például egy egyszerű gráf (ezekben az oszlopokban nem tudok rajzokat használni, ezért leírom a gráf íveit):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Ez a gráf hat csomóponttal (A-F) és nyolc ívvel rendelkezik. A következő Python adatszerkezettel ábrázolható:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Ez egy szótár, amelynek kulcsai a gráf csomópontjai. Minden kulcshoz tartozó érték egy lista, amely azokat a csomópontokat tartalmazza, amelyek az adott csomópontból közvetlen ívvel kapcsolódnak. Ez a lehető legegyszerűbb (mégegyszerűbb, a csomópontokat nevek helyett számokkal is ábrázolhatnánk, de a nevek kényelmesebbek, és könnyen több információ, például városnevek hordozására is alkalmasak).
Írjunk egy egyszerű függvényt két csomópont közötti útvonal meghatározására. Ez egy gráfot és a kezdő- és végcsomópontokat veszi argumentumként. Visszaadja az útvonalat alkotó csomópontok listáját (beleértve a kezdő- és végcsomópontokat).Ha nem talál útvonalat, akkor None-t ad vissza. Ugyanaz a csomópont nem fordul elő többször a visszaadott útvonalon (azaz nem tartalmaz ciklusokat). Az algoritmus egy fontos technikát használ, amit visszalépésnek nevezünk: minden lehetőséget sorban kipróbál, amíg nem talál megoldást.
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
Mintafuttatás (a fenti gráf felhasználásával):
>>> find_path(graph, 'A', 'D') >>>
A második “if” utasításra csak abban az esetben van szükség, ha vannak olyan csomópontok, amelyek ívek végpontjaként szerepelnek, de maguknak nincs kimenő ívük, és egyáltalán nem szerepelnek a gráfban. Az ilyen csomópontok is lehetnek a gráfban, a kimenő ívek üres listájával, de néha kényelmesebb, ha ezt nem követeljük meg.
Megjegyezzük, hogy míg a felhasználó a find_path()-t három argumentummal hívja meg, addig az önmagát egy negyedik argumentummal hívja meg: a már bejárt útvonal.Ennek az argumentumnak az alapértelmezett értéke az üres lista, ”, ami azt jelenti, hogy még nem jártak be csomópontokat. Ez az argumentum a ciklusok elkerülésére szolgál (az első ‘if’ a ‘for’ cikluson belül). A ‘path’ argumentum nem módosul: a “path = path + ” hozzárendelés új listát hoz létre. Ha helyette “path.append(start)”-t írtunk volna, akkor a hívóprogramban módosítottuk volna a’path’ változót, katasztrofális eredménnyel. (Tuplik használatával biztosak lehettünk volna abban, hogy ez nem történik meg, annak árán, hogy “path = path + (start,)” kellett volna írnunk, mivel “(start)” nem egy singleton tuple — ez csak egy zárójeles kifejezés.)
Egyszerűen megváltoztathatjuk ezt a függvényt úgy, hogy az első megtalált út helyett az összes útvonal listáját adja vissza (ciklusok nélkül):
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
Példafuttatás:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Egy másik változat a legrövidebb utat találja meg:
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
Példafuttatás:
>>> find_shortest_path(graph, 'A', 'D') >>>
Ezek a függvények a lehető legegyszerűbbek. Mégis közel optimálisak (Pythonban írt kód esetén). Egy másik Python Patterns rovatban megpróbálom elemezni a futási sebességüket és javítani a teljesítményüket, több kód árán.
UPDATE: Eryk Kopczyński rámutatott, hogy ezek a függvények nem optimálisak. Éppen ellenkezőleg, “ez a program exponenciális idő alatt fut,míg a find_shortest_path lineáris idő alatt elvégezhető a BFS segítségével . Ráadásul a lineáris BFS egyszerűbb:”
# 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)
Megjegyezzük, hogy ez furcsa formátumban adja vissza az utat, pl.,, 'B'], 'D']. Különösen alen(find_shortest_path(graph, 'A', 'D'))adja a helytelen választ (2, mert a külső lista hossza 2). Ez azért van, mert az append, next]-ként történikdist+helyett. A második módszer kvadratikus időt és memóriát használna, de viszonylag kis gráfok esetén még mindig jónak kell lennie;egyébként könnyű a listát a helyes formátumba alakítani.
Egy másik variáció az lenne, ha több adatabsztrakciót adnánk hozzá: létrehoznánk egy osztályt a gráfok reprezentálására, amelynek metódusai megvalósítják a különböző algoritmusokat. Bár ez a strukturált programozás iránti vágynak felel meg, nem teszi hatékonyabbá a kódot (épp ellenkezőleg). Könnyebbé teszi a csomópontok vagy ívek különböző címkékkel való ellátását, és olyan algoritmusok hozzáadását, amelyek figyelembe veszik ezeket a címkéket (pl. két város közötti legrövidebb útvonal megtalálása a térképen). Ez is egy másik rovat témája lesz.