Det finns flera sätt att implementera en riktad graf i Python, var och en med sina egna fördelar och nackdelar beroende på de specifika applikations- och prestandakraven. Här är tre vanliga tillvägagångssätt:
1. Adjacenslista (med hjälp av en ordbok)
* koncept: Varje nod i grafen är en nyckel i en ordbok. Värdet associerat med varje nyckel (nod) är en lista över dess grannar (noderna som nyckelnoden har en riktad kant till). Detta är ofta den mest effektiva och vanligt använda metoden, särskilt för glesa grafer (grafer med relativt få kanter).
* Implementering:
`` `python
klass DirectedGraph:
def __init __ (själv):
self.graph ={} # ordlista för att lagra anställningslistan
def add_node (self, node):
Om nod inte i själv.graph:
self.graph [node] =[]
def add_edge (self, from_node, to_node):
om från_node inte i self.graph:
self.add_node (från_node)
om till_node inte i self.graph:
self.add_node (to_node) # eller höja ett fel om du kräver att noder uttryckligen läggs till
self.graph [from_node]. append (to_node)
def get_neighbors (self, node):
Om nod i self.graph:
returnera self.graph [nod]
annan:
returnera [] # eller höja ett fel, beroende på önskat beteende
def remove_node (self, node):
Om nod i self.graph:
del self.graph [node]
# Ta bort kanter som pekar * till * den raderade noden
för n i self.graph:
Om nod i self.graph [n]:
self.graph [n] .remove (nod)
def remove_edge (self, from_node, to_node):
om från_node i self.graph och to_node in self.graph [from_node]:
self.graph [from_node]. remove (to_node)
def has_node (self, node):
returnera noden i self.graph
def has_edge (self, from_node, to_node):
returnera från_node i self.graph och to_node in self.graph [from_node]
def __str __ (själv):
return Str (self.graph)
# Exempelanvändning
graf =DirecedGraph ()
graf.add_node ("a")
graf.add_node ("B")
graf.add_node ("C")
graf.add_edge ("a", "b")
graf.add_edge ("a", "c")
graf.add_edge ("b", "c")
utskrift (graf) # output:{'a':['b', 'c'], 'b':['c'], 'c':[]}
utskrift (graf.get_neighbors ("a")) # output:['b', 'c']
utskrift (graf.has_edge ("a", "b")) # output:true
graf.remove_edge ("a", "b")
utskrift (graf) # output:{'a':['c'], 'b':['c'], 'c':[]}
graf.remove_node ("b")
utskrift (graf) # output:{'a':['c'], 'c':[]}
`` `
* Fördelar:
* Enkelt att implementera.
* Effektiv för glesa grafer.
* Lätt att hitta grannar till en nod.
* Att lägga till och ta bort noder/kanter kan vara relativt effektiva (O (1) i genomsnitt för ordböcker, O (n) i värsta fall för `remove_node 'på grund av iterering genom andra nodernas adjacenslistor för att ta bort kanter som pekar till den borttagna noden).
* Nackdelar:
* Mindre effektiv för täta grafer (grafer med nästan alla möjliga kanter).
* Att kontrollera om en kant finns (annat än att använda `has_edge ()`) kräver iterering genom grannlistan över källnoden, som kan vara o (n) i värsta fall.
2. Adjektivmatris (med en 2D -lista/array)
* koncept: Använd en 2D -matris (eller en lista med listor i Python) där `Matrix [i] [j]` är 1 (eller `sant ') om det finns en riktad kant från nod` i' till nod `j`, och 0 (eller` falsk ') annars.
* Implementering:
`` `python
Klass DirectedGraphMatrix:
def __init __ (self, num_nodes):
self.num_nodes =num_nodes
self.matrix =[[0] * num_nodes för _ inom räckvidd (num_nodes)]
def add_edge (self, from_node, to_node):
om 0 <=från_node
self.matrix [från_node] [to_node] =1
annan:
Skriv ut ("Ogiltiga nodindex.")
def remove_edge (self, from_node, to_node):
om 0 <=från_node
self.matrix [från_node] [to_node] =0
annan:
Skriv ut ("Ogiltiga nodindex.")
def has_edge (self, from_node, to_node):
om 0 <=från_node
returnera self.matrix [från_node] [to_node] ==1
annan:
Skriv ut ("Ogiltiga nodindex.")
returnera falskt
def get_neighbors (self, node):
om 0 <=nod
Grannar =[]
för i inom räckvidd (self.num_nodes):
om self.matrix [node] [i] ==1:
Grannar.Append (i)
Återvänd grannar
annan:
tryck ("Ogiltigt nodindex.")
returnera []
def __str __ (själv):
return '\ n'.join ([' '.join (karta (str, rad)) för rad i self.matrix])
# Exempelanvändning:
Graf =DirectedGraphMatrix (4) # Graf med 4 noder
graf.add_edge (0, 1)
graf.add_edge (0, 2)
graf.add_edge (1, 3)
tryck (graf)
# Output:
# 0 1 1 0
# 0 0 0 1
# 0 0 0 0
# 0 0 0 0
tryck (graf.has_edge (0, 1)) # utgång:true
utskrift (graf.get_neighbors (0)) # utgång:[1, 2]
`` `
* Fördelar:
* Snabbt för att kontrollera om en kant finns (O (1)).
* Enkelt att implementera.
* Nackdelar:
* Kräver att förebygga antalet noder. Det kan modifieras för att ändra storlek dynamiskt, men det kan bli kostsamt.
* Ineffektiv för glesa grafer (avfall mycket minne).
* Att lägga till/ta bort noder kan vara dyra eftersom du måste ändra storlek på hela matrisen.
3. Använda ett grafbibliotek (t.ex. Networkx)
* koncept: Utnyttja befintliga grafbibliotek som ger optimerade implementeringar och en mängd grafalgoritmer. Networkx är ett populärt val.
* Implementering:
`` `python
Importera Networkx som NX
# Skapa en riktad graf
graf =nx.digraph ()
# Lägg till noder
graf.add_nodes_from (["a", "b", "c"])
# Lägg till kanter
graf.add_edge ("a", "b")
graf.add_edge ("a", "c")
graf.add_edge ("b", "c")
# Kontrollera om en kant finns
utskrift (graf.has_edge ("a", "b")) # output:true
# Få grannar
utskrift (lista (graf.successors ("a"))) # output:['b', 'c'] (efterföljare =utgående grannar)
# Ta bort en kant
graf.remove_edge ("a", "b")
tryck (graf.has_edge ("a", "b")) # utgång:falsk
# Ta bort en nod
graf.remove_node ("b")
utskrift (graf.nodes ()) # output:['a', 'c']
# Du kan rita grafen (kräver matplotlib)
# Importera matplotlib.pyplot som plt
# nx.draw (graf, with_labels =true, node_color ="skyBlue", node_size =1500, font_size =15)
# plt.show ()
`` `
* Fördelar:
* Mogna och väl testade bibliotek.
* Ger en rik uppsättning grafalgoritmer (kortaste väg, centralitetsåtgärder etc.).
* Enklare att utföra komplexa grafoperationer.
* Stöder grafvisualisering.
* Nackdelar:
* Lite omkostnader jämfört med att implementera din egen grafstruktur.
* Kräver installation av ett externt bibliotek.
Att välja rätt implementering
* glesa grafer: Adjektivlista är i allmänhet det bästa valet.
* täta grafer: Adjacency Matrix kan vara snabbare för kanterkontroller, men den förbrukar mer minne. Tänk på avvägningar.
* komplexa grafoperationer: Använd NetworkX eller ett annat grafbibliotek. Om du behöver implementera anpassade algoritmer eller arbetar med mycket stora grafer, kanske du vill använda adjacenslistan eller matrismetoderna, men du måste implementera algoritmerna själv.
* enkla uppgifter: Om du bara behöver grundläggande grafrepresentation och traversal räcker det ofta.
Nyckelöverväganden:
* Minnesanvändning: Adjacenslistor är mer minneseffektiva för glesa grafer. Adjektivmatriser kan använda mycket minne, särskilt för stora, glesa grafer.
* Prestanda: Adjektivmatriser ger O (1) kantuppslag, medan adjacenslistor kräver o (n) i värsta fall (där n är antalet grannar).
* användarvänlighet: Grafbibliotek ger ett mer bekvämt och funktionsrikt API.
* Mutabilitet kontra immutabilitet: Bestäm om du ofta behöver ändra grafstrukturen. Adjacenslistor och matriser är muterbara. Networkx -grafer är också muterbara. Om du behöver en oföränderlig graf kan du behöva utforska alternativa datastrukturer.
* Vägda grafer: Om du behöver representera vägda kanter kan du ändra anställningslistan eller matrisen för att lagra kantvikterna. Till exempel kan du i adjacenslistan lagra en ordbok för `to_node:vikt` istället för bara en lista med noder. NetworkX har inbyggt stöd för vägda grafer.
Innan du implementerar en graf, överväg noggrant kraven i ditt specifika problem för att välja den lämpligaste datastrukturen och algoritmerna. Om du är osäker, börja med justeringslistan, eftersom det är en bra lösning av allmänt syfte. Om du räknar med att du behöver mer avancerade grafalgoritmer är Networkx -biblioteket ofta ett bra val.
