Atenție
Această pagină rămâne aici din motive istorice și poate conține informații învechite sau incorecte.
Note de modificare: 2/22/98, 3/2/98, 12/4/00: Această versiune a acestui eseu corectează mai multe erori de cod. 6/10/19: Retragerea luifind_shortest_pathca fiind „aproape optim”. 8/11/19: Corectarea utilizării accidentale afind_graph()în loc defind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
Grafurile sunt rețele formate din noduri conectate prin muchii sau arce. În grafurile indirecte, conexiunile dintre noduri au o direcție și se numesc arce; în grafurile nedirecționate, conexiunile nu au nicio direcție și se numesc muchii. Vom discuta în principal grafurile dirijate. Algoritmii în grafuri includ găsirea unei căi între două noduri, găsirea celei mai scurte căi între două noduri, determinarea ciclurilor din graf (un ciclu este o cale nevidă de la un nod la el însuși), găsirea unei căi care ajunge la toate nodurile (faimoasa „problemă a vânzătorului ambulant”) etc. Uneori, nodurile sau arcele unui graf au ponderi sau costuri asociate, iar noi suntem interesați să găsim cea mai ieftină cale.
Există o literatură considerabilă despre algoritmii grafurilor, care reprezintă o parte importantă a matematicii discrete. Grafurile au, de asemenea, multe utilizări practice în algoritmii de calculator. Exemple evidente pot fi găsite în gestionarea rețelelor, dar exemplele abundă în multe alte domenii. De exemplu, relațiile dintre apelant și apelat într-un program de calculator pot fi văzute ca un graf (în care ciclurile indică recursivitatea, iar nodurile inaccesibile reprezintă codul mort).
Puține limbaje de programare oferă suport direct pentru grafuri ca tip de date, iar Python nu face excepție. Cu toate acestea, grafurile sunt ușor de construit din listeși dicționare. De exemplu, iată un grafic simplu (nu pot folosi desene în aceste coloane, așa că scriu arcele graficului):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Acest grafic are șase noduri (A-F) și opt arce. El poate fi reprezentat prin următoarea structură de date Python:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Este un dicționar ale cărui chei sunt nodurile grafului. Pentru fiecare cheie, valoarea corespunzătoare este o listă care conține nodurile care sunt conectate printr-un arc direct de la acest nod. Acest lucru este cât se poate de simplu (chiar mai simplu, nodurile ar putea fi reprezentate prin numere în loc de nume, dar numele sunt mai convenabile și pot fi ușor de făcut să conțină mai multe informații, cum ar fi numele orașelor).
Să scriem o funcție simplă pentru a determina o cale între două noduri. Aceasta primește ca argumente un grafic și nodurile de început și de sfârșit. Aceasta va returna o listă de noduri (inclusiv nodurile de început și de sfârșit) care alcătuiesc calea.În cazul în care nu se găsește nicio cale, aceasta returnează None. Același nod nu va apărea de mai multe ori pe traseul returnat (adică nu va conține cicluri). Algoritmul folosește o tehnică importantă numită „backtracking”: încearcă fiecare posibilitate pe rând până când găsește o soluție.
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
Un exemplu de execuție (folosind graficul de mai sus):
>>> find_path(graph, 'A', 'D') >>>
A doua afirmație „if” este necesară doar în cazul în care există noduri care sunt listate ca puncte finale pentru arce, dar care nu au ele însele arce de ieșire și care nu sunt listate deloc în grafic. Astfel de noduri ar putea, de asemenea, să fie conținute în graf, cu o listă goală de arce de ieșire, dar uneori este mai convenabil să nu se ceară acest lucru.
Rețineți că, în timp ce utilizatorul apelează find_path() cu trei argumente, acesta se apelează pe sine cu un al patrulea argument: calea care a fost deja parcursă.Valoarea implicită pentru acest argument este lista goală, ”, ceea ce înseamnă că niciun nod nu a fost încă parcurs. Acest argument este utilizat pentru a evita ciclurile (primul „if” din cadrul buclei „for”). Argumentul „path” nu este modificat: atribuirea „path = path + ” creează o nouă listă. Dacă am fi scris în schimb „path.append(start)”, am fi modificat variabila „path” în apelant, cu rezultate dezastruoase. (Utilizând tuple, am fi putut fi siguri că acest lucru nu se va întâmpla, cu prețul de a fi nevoiți să scriem „path = path + (start,)”, deoarece „(start)” nu este un tuple singleton – este doar o expresie între paranteze.)
Este simplu să modificăm această funcție pentru a returna o listă cu toate căile (fără cicluri) în loc de prima cale pe care o găsește:
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
Un exemplu de execuție:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
O altă variantă găsește cea mai scurtă cale:
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
Exemplu de execuție:
>>> find_shortest_path(graph, 'A', 'D') >>>
Aceste funcții sunt cât se poate de simple. Cu toate acestea, ele sunt aproapeoptime (pentru codul scris în Python). Într-o altă coloană despre modelele Python, voi încerca să analizez viteza lor de rulare și să le îmbunătățesc performanța, cu prețul unui cod mai mare.
UPDATE: Eryk Kopczyński a subliniat că aceste funcții nu sunt optime. Dimpotrivă, „acest program rulează în timp exponențial,în timp ce find_shortest_path poate fi realizat în timp liniar folosind BFS . În plus, un BFS liniar este mai simplu:”
# 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)
Rețineți că acesta returnează calea într-un format ciudat, de exemplu,, 'B'], 'D']. În special,len(find_shortest_path(graph, 'A', 'D'))va da un răspuns incorect (2, deoarece lista exterioară este de lungime 2). Acest lucru se datorează faptului că adăugarea se face sub forma, next]în loc dedist+. Cea de-a doua metodă ar folosi timp și memorie cvadrantă, dar totuși ar trebui să fie în regulă pentru grafuri relativ mici;altfel, este ușor de transformat lista în formatul corect.
O altă variantă ar fi să se adauge mai multă abstractizare a datelor: să se creeze o clasă care să reprezinte grafuri, ale cărei metode să implementeze diverși algoritmi. Deșiacest lucru face apel la dorința de programare structurată, nu face codul mai eficient (dimpotrivă). Aceasta ușurează adăugarea diferitelor etichete la noduri sau arce și adăugarea de algoritmi care iau în considerare aceste etichete (de exemplu, pentru a găsi cea mai scurtă rută între două orașe pe o hartă). Și acesta va fi subiectul unei alte rubrici.
.