Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Zoznam susedstva (pomocou slovníka)
* koncept: Každý uzol v grafe je kľúčom v slovníku. Hodnota spojená s každým kľúčom (uzol) je zoznam jeho susedov (uzly, na ktoré má kľúčový uzol smerovanú hranu). Toto je často najúčinnejšia a bežne používaná metóda, najmä pre riedke grafy (grafy s relatívne malými hrami).
* implementácia:
`` `Python
Trieda režisér:
def __init __ (self):
self.graph ={} # Dictionary na uloženie zoznamu susediacich
def add_node (self, uzol):
Ak uzol nie je v self.graph:
self.graph [uzol] =[]
def add_edge (self, from_node, to_node):
Ak z_node nie je v self.graph:
self.add_node (from_node)
Ak to_node nie je v self.graph:
self.add_node (to_node) # alebo zdvihnite chybu, ak požadujete, aby ste sa najskôr explicitne pridali uzly
self.graph [from_node] .Append (to_node)
def get_neighbors (self, uzol):
Ak uzol v self.graph:
návrat self.graph [uzol]
inak:
Vráťte [] # alebo zdvihnúť chybu v závislosti od požadovaného správania
def remove_node (self, uzol):
Ak uzol v self.graph:
del self.graph [uzol]
# Odstráňte hrany smerujúce * na * odstránený uzol
pre n v self.graph:
Ak uzol v self.graph [n]:
self.graph [n] .Remove (uzol)
def remove_edge (self, from_node, to_node):
Ak z_node v self.graph a to_node in self.graph [from_node]:
self.graph [from_node] .Remove (to_node)
def has_node (self, uzol):
návratový uzol v self.graph
def has_edge (self, from_node, to_node):
Návrat z_node v self.graph a to_node v self.graph [from_node]
def __str __ (self):
návrat Str (self.graph)
# Príklad použitia
Graph =regeDoPraph ()
Graph.add_node („A“)
Graph.add_node ("B")
Graph.add_node ("C")
Graph.add_edge („A“, „B“)
Graph.add_edge („A“, „C“)
Graph.add_edge ("B", "C")
tlač (graf) # výstup:{'a':['b', 'c'], 'b':['c'], 'c':[]}
Print (Graph.get_neighbors ("A")) # výstup:['B', 'C']
tlač (graf.has_edge ("a", "b")) # výstup:true
Graph.Remove_edge („A“, „B“)
tlač (graf) # výstup:{'a':['c'], 'b':['c'], 'c':[]}
Graph.Remove_node ("B")
tlač (graf) # výstup:{'a':['c'], 'c':[]}
`` `
* Výhody:
* Jednoduché implementácia.
* Efektívne pre riedke grafy.
* Ľahko nájsť susedov uzla.
* Pridanie a odstránenie uzlov/hrán môže byť relatívne účinné (O (1) v priemere pre slovníky, o (n) v najhoršom prípade pre `remove_node` v dôsledku iterovania prostredníctvom zoznamov iných uzlov, aby sa odstránili hrany smerujúce do odstráneného uzla).
* Nevýhody:
* Menej efektívne pre husté grafy (grafy s takmer všetkými možnými hranami).
* Kontrola, či existuje hrana (okrem použitia `has_edge ()`), vyžaduje iterovanie prostredníctvom zoznamu susedov zdrojového uzla, ktorý môže byť v najhoršom prípade O (n).
2. Matica susediacej (pomocou 2D zoznamu/poľa)
* koncept: Použite 2D pole (alebo zoznam zoznamov v Pythone), kde „matica [i] [j]` je 1 (alebo `true`), ak existuje smerovaná hrana z uzla` i` na uzol `j` a 0 (alebo` false`) inak.
* implementácia:
`` `Python
Trieda režisérka:
def __init __ (self, num_nodes):
self.num_nodes =num_nodes
self.matrix =[[0] * num_nodes pre _ v rozsahu (num_nodes)]
def add_edge (self, from_node, to_node):
Ak 0 <=from_node
inak:
tlač („Indexné indexy uzlov“.)
def remove_edge (self, from_node, to_node):
Ak 0 <=from_node
inak:
tlač („Indexné indexy uzlov“.)
def has_edge (self, from_node, to_node):
Ak 0 <=from_node
inak:
tlač („Indexné indexy uzlov“.)
nepravdivý
def get_neighbors (self, uzol):
Ak 0 <=uzol
pre i v rozsahu (self.num_nodes):
Ak self.matrix [uzol] [i] ==1:
susedia.ppend (i)
susedia
inak:
tlač („Invalidný index uzlov“)
návrat []
def __str __ (self):
return '\ n'.join ([' '.Boin (map (str, row)) pre riadok v self.matrix])
# Príklad použitia:
Graph =DirectedGraphMatrix (4) # Graf so 4 uzlami
Graph.add_edge (0, 1)
Graph.add_edge (0, 2)
Graph.add_edge (1, 3)
tlač (graf)
# Výstup:
# 0 1 1 0
# 0 0 0 1
# 0 0 0 0
# 0 0 0 0
tlač (graf.has_edge (0, 1)) # výstup:true
Print (Graph.get_neighbors (0)) # výstup:[1, 2]
`` `
* Výhody:
* Rýchlo skontrolovať, či existuje hrana (o (1)).
* Jednoduché implementácia.
* Nevýhody:
* Vyžaduje preddefinovanie počtu uzlov. Môže sa zmeniť tak, aby dynamicky zmenila veľkosť veľkosti, ale to sa môže stať nákladným.
* Neefektívne pre riedke grafy (odpady veľa pamäte).
* Pridanie/odstránenie uzlov môže byť drahé, pretože musíte zmeniť veľkosť celej matice.
3. Pomocou grafovej knižnice (napr. NetworkX)
* koncept: Využite existujúce knižnice grafov, ktoré poskytujú optimalizované implementácie a množstvo algoritmov grafov. Networkx je obľúbenou voľbou.
* implementácia:
`` `Python
import Networkx ako NX
# Vytvorte nasmerovaný graf
graf =nx.digraph ()
# Pridajte uzly
Graph.add_nodes_from (["A", "B", "C"])
# Pridajte hrany
Graph.add_edge („A“, „B“)
Graph.add_edge („A“, „C“)
Graph.add_edge ("B", "C")
# Skontrolujte, či existuje hrana
tlač (graf.has_edge ("a", "b")) # výstup:true
# Získajte susedov
tlač (zoznam (graph.successors ("a"))) # výstup:['b', 'c'] (nástupcovia =odchádzajúci susedia)
# Odstráňte okraj
Graph.Remove_edge („A“, „B“)
tlač (graf.has_edge ("a", "b")) # výstup:false
# Odstráňte uzol
Graph.Remove_node ("B")
Print (Graph.nodes ()) # výstup:['A', 'C']
# Môžete nakresliť graf (vyžaduje matplotlib)
# importovať matplolib.pyplot ako plt
# nx.draw (graf, with_labels =true, node_color ="skyBlue", node_size =1500, font_size =15)
# plt.show ()
`` `
* Výhody:
* Zrelá a dobre testovaná knižnica.
* Poskytuje bohatú sadu grafových algoritmov (najkratšia cesta, miery centrálnosti atď.).
* Ľahšie vykonávate komplexné operácie grafov.
* Podporuje vizualizáciu grafov.
* Nevýhody:
* Mierne režijné náklady v porovnaní s implementáciou vlastnej štruktúry grafu.
* Vyžaduje inštaláciu externej knižnice.
Výber správnej implementácie
* riedke grafy: Zoznam susedstva je vo všeobecnosti najlepšou voľbou.
* husté grafy: Matica susediacej matice môže byť rýchlejšia pre kontroly existencie okrajov, ale spotrebuje viac pamäte. Zvážte kompromisy.
* Komplexné grafové operácie: Používajte Networkx alebo inú knižnicu grafov. Ak potrebujete implementovať vlastné algoritmy alebo pracujete s veľmi veľkými grafmi, možno budete chcieť použiť zoznam susedných alebo maticových prístupov, ale budete musieť sami implementovať algoritmy.
* jednoduché úlohy: Ak potrebujete iba základnú reprezentáciu a prechádzanie grafom, zoznam susedných síl je často dostatočný.
Kľúčové úvahy:
* Použitie pamäte: Zoznamy susedstva sú pre riedke grafy efektívnejšie. Matice v susedstve môžu používať veľa pamäte, najmä pre veľké, riedke grafy.
* Výkon: Matice susedných síl poskytujú O (1) vyhľadávanie na okraji, zatiaľ čo zoznamy susedných síl vyžadujú O (n) v najhoršom prípade (kde n je počet susedov).
* ľahké použitie: Grafové knižnice poskytujú pohodlnejšie API bohaté na funkcie.
* Mentabilita vs. nemeniteľnosť: Rozhodnite sa, či potrebujete často upraviť štruktúru grafu. Zoznamy a matice sú menené. Grafy Networkx sú tiež menené. Ak potrebujete nemenný graf, možno budete musieť preskúmať alternatívne dátové štruktúry.
* vážené grafy: Ak potrebujete reprezentovať vážené hrany, môžete upraviť zoznam susedných síl alebo matice na uloženie závažia okrajov. Napríklad v zozname susedných síl by ste mohli uložiť slovník `to_node:hmotnosť namiesto iba zoznamu uzlov. Networkx má vstavanú podporu pre vážené grafy.
Pred implementáciou grafu opatrne zvážte požiadavky vášho konkrétneho problému, aby ste si vybrali najvhodnejšiu štruktúru údajov a algoritmy. Ak máte pochybnosti, začnite so zoznamom susedstva, pretože je to dobré riešenie všeobecného účtu. Ak očakávate potrebu pokročilejších algoritmov grafov, knižnica NetworkX je často dobrou voľbou.