1. Nabijheidslijst (met behulp van een woordenboek)

* Concept: Elk knooppunt in de grafiek is een sleutel in een woordenboek. De waarde die aan elke sleutel (knooppunt) is gekoppeld, is een lijst van zijn buren (de knooppunten waarnaar het sleutelknooppunt een gerichte rand heeft). Dit is vaak de meest efficiënte en meest gebruikte methode, vooral voor dunne grafieken (grafieken met relatief weinig randen).

* Implementatie:

```python

klasse DirectedGraph:

def __init__(zelf):

self.graph ={} # Woordenboek om de aangrenzende lijst op te slaan

def add_node(zelf, knooppunt):

als knooppunt niet in self.graph:

zelf.grafiek[node] =[]

def add_edge(self, from_node, to_node):

if from_node niet in self.graph:

self.add_node(van_node)

if to_node niet in self.graph:

self.add_node(to_node) # Of geef een foutmelding als u wilt dat knooppunten eerst expliciet worden toegevoegd

self.graph[van_knooppunt].append(naar_knooppunt)

def get_neighbors(self, node):

als knooppunt in self.graph:

return self.graph[node]

anders:

return [] # Of geef een foutmelding, afhankelijk van het gewenste gedrag

def remove_node(zelf, knooppunt):

als knooppunt in self.graph:

del self.graph[node]

# Verwijder randen die *naar* het verwijderde knooppunt wijzen

voor n in zelf.grafiek:

if knooppunt in self.graph[n]:

self.graph[n].verwijder(knooppunt)

def remove_edge(self, from_node, to_node):

if from_node in self.graph en to_node in self.graph[from_node]:

self.graph[van_knooppunt].verwijder(naar_knooppunt)

def has_node(zelf, knooppunt):

retourknooppunt in self.graph

def has_edge(self, from_node, to_node):

retourneer from_node in self.graph en to_node in self.graph[from_node]

def __str__(zelf):

return str(zelf.grafiek)

# Voorbeeldgebruik

grafiek =DirectedGraph()

graph.add_node("A")

graph.add_node("B")

grafiek.add_node("C")

graph.add_edge("A", "B")

graph.add_edge("A", "C")

graph.add_edge("B", "C")

print(grafiek) # Uitvoer:{'A':['B', 'C'], 'B':['C'], 'C':[]}

print(graph.get_neighbors("A")) # Uitvoer:['B', 'C']

print(graph.has_edge("A", "B")) # Uitvoer:Waar

graph.remove_edge("A", "B")

print(grafiek) # Uitvoer:{'A':['C'], 'B':['C'], 'C':[]}

graph.remove_node("B")

print(grafiek) # Uitvoer:{'A':['C'], 'C':[]}

```

* Voordelen:

* Eenvoudig te implementeren.

* Efficiënt voor schaarse grafieken.

* Gemakkelijk om buren van een knooppunt te vinden.

* Het toevoegen en verwijderen van knooppunten/randen kan relatief efficiënt zijn (gemiddeld O(1) voor woordenboeken, O(n) in het slechtste geval voor `remove_node' vanwege het doorlopen van de aangrenzende lijsten van andere knooppunten om randen te verwijderen die naar het verwijderde knooppunt wijzen).

* Nadelen:

* Minder efficiënt voor compacte grafieken (grafieken met bijna alle mogelijke randen).

* Om te controleren of er een rand bestaat (anders dan het gebruik van `has_edge()`), moet je de lijst met buren van het bronknooppunt doorlopen, wat in het ergste geval O(n) kan zijn.

2. Nabijheidsmatrix (met behulp van een 2D-lijst/array)

* Concept: Gebruik een 2D-array (of een lijst met lijsten in Python) waarbij `matrix[i][j]` 1 (of `True`) is als er een gerichte rand is van knooppunt `i` naar knooppunt `j`, en anders 0 (of `False`).

* Implementatie:

```python

klasse DirectedGraphMatrix:

def __init__(zelf, aantal_nodes):

self.num_nodes =aantal_nodes

self.matrix =[[0] * aantal_nodes voor _ binnen bereik (aantal_nodes)]

def add_edge(self, from_node, to_node):

als 0 <=from_node zelf.matrix[van_knooppunt][naar_knooppunt] =1

anders:

print("Ongeldige knooppuntindexen.")

def remove_edge(self, from_node, to_node):

als 0 <=from_node zelf.matrix[van_knooppunt][naar_knooppunt] =0

anders:

print("Ongeldige knooppuntindexen.")

def has_edge(self, from_node, to_node):

als 0 <=from_node return self.matrix[van_knooppunt][naar_knooppunt] ==​​1

anders:

print("Ongeldige knooppuntindexen.")

terugkeer Vals

def get_neighbors(self, node):

als 0 <=knooppunt buren =[]

voor i binnen bereik(self.num_nodes):

als zelf.matrix[knooppunt][i] ==1:

buren.append(i)

buren terugbrengen

anders:

print("Ongeldige knooppuntindex.")

opbrengst []

def __str__(zelf):

return '\n'.join([' '.join(map(str, rij)) voor rij in self.matrix])

# Voorbeeldgebruik:

graph =DirectedGraphMatrix(4) # Grafiek met 4 knooppunten

grafiek.add_edge(0, 1)

grafiek.add_edge(0, 2)

grafiek.add_edge(1, 3)

afdrukken(grafiek)

# Uitgang:

# 0 1 1 0

# 0 0 0 1

# 0 0 0 0

# 0 0 0 0

print(graph.has_edge(0, 1)) # Uitvoer:Waar

print(graph.get_neighbors(0)) # Uitvoer:[1, 2]

```

* Voordelen:

* Snel controleren of er een rand bestaat (O(1)).

* Eenvoudig te implementeren.

* Nadelen:

* Vereist vooraf definiëren van het aantal knooppunten. Het kan worden aangepast om het formaat dynamisch te wijzigen, maar dat kan kostbaar worden.

* Inefficiënt voor schaarse grafieken (verspilt veel geheugen).

* Het toevoegen/verwijderen van knooppunten kan kostbaar zijn, omdat je de grootte van de hele matrix moet wijzigen.

3. Een grafiekbibliotheek gebruiken (bijvoorbeeld NetworkX)

* Concept: Maak gebruik van bestaande grafiekbibliotheken die geoptimaliseerde implementaties en een schat aan grafiekalgoritmen bieden. NetworkX is een populaire keuze.

* Implementatie:

```python

importeer netwerkx als nx

# Maak een gerichte grafiek

grafiek =nx.DiGraph()

# Knooppunten toevoegen

graph.add_nodes_from(["A", "B", "C"])

# Randen toevoegen

graph.add_edge("A", "B")

graph.add_edge("A", "C")

graph.add_edge("B", "C")

# Controleer of er een rand bestaat

print(graph.has_edge("A", "B")) # Uitvoer:Waar

# Zoek buren

print(list(graph.successors("A"))) # Uitvoer:['B', 'C'] (Opvolgers =uitgaande buren)

# Verwijder een rand

graph.remove_edge("A", "B")

print(graph.has_edge("A", "B")) # Uitvoer:False

# Verwijder een knooppunt

graph.remove_node("B")

print(graph.nodes()) # Uitvoer:['A', 'C']

# U kunt de grafiek tekenen (vereist matplotlib)

# importeer matplotlib.pyplot als plt

# nx.draw(grafiek, with_labels=True, node_color ="hemelsblauw", node_size =1500, font_size =15)

# plt.show()

```

* Voordelen:

* Volwassen en goed geteste bibliotheek.

* Biedt een rijke reeks grafiekalgoritmen (kortste pad, centraliteitsmetingen, enz.).

* Gemakkelijker om complexe grafiekbewerkingen uit te voeren.

* Ondersteunt grafiekvisualisatie.

* Nadelen:

* Geringe overhead vergeleken met het implementeren van uw eigen grafiekstructuur.

* Vereist installatie van een externe bibliotheek.

De juiste implementatie kiezen

* Spaarzame grafieken: Aangrenzende lijst is over het algemeen de beste keuze.

* Dichte grafieken: De aangrenzende matrix kan sneller zijn voor controles op het bestaan ​​van de rand, maar verbruikt meer geheugen. Denk eens aan de afwegingen.

* Complexe grafiekbewerkingen: Gebruik NetworkX of een andere grafiekbibliotheek. Als u aangepaste algoritmen moet implementeren of met zeer grote grafieken werkt, wilt u misschien de aangrenzende lijst of matrixbenaderingen gebruiken, maar u zult de algoritmen zelf moeten implementeren.

* Eenvoudige taken: Als u alleen maar basisgrafiekrepresentatie en -doorgang nodig heeft, is de aangrenzende lijst vaak voldoende.

Belangrijke overwegingen:

* Geheugengebruik: Aangrenzende lijsten zijn geheugenefficiënter voor schaarse grafieken. Aangrenzende matrices kunnen veel geheugen gebruiken, vooral voor grote, schaarse grafieken.

* Prestaties: Aangrenzende matrices bieden O(1) edge lookup, terwijl aangrenzende lijsten in het ergste geval O(n) vereisen (waarbij n het aantal buren is).

* Gebruiksgemak: Grafiekbibliotheken bieden een handigere en functierijke API.

* Veranderlijkheid versus onveranderlijkheid: Bepaal of u de grafiekstructuur regelmatig moet wijzigen. Aangrenzende lijsten en matrices zijn veranderlijk. NetworkX-grafieken zijn ook veranderlijk. Als u een onveranderlijke grafiek nodig heeft, moet u mogelijk alternatieve gegevensstructuren verkennen.

* Gewogen grafieken: Als u gewogen randen moet weergeven, kunt u de aangrenzende lijst of matrix wijzigen om de randgewichten op te slaan. In de lijst met aangrenzende punten kunt u bijvoorbeeld een woordenboek met `naar_knooppunt:gewicht` opslaan in plaats van alleen maar een lijst met knooppunten. NetworkX heeft ingebouwde ondersteuning voor gewogen grafieken.

Voordat u een grafiek implementeert, moet u zorgvuldig de vereisten van uw specifieke probleem overwegen om de meest geschikte gegevensstructuur en algoritmen te kiezen. Als u twijfelt, begin dan met de lijst met aangrenzende gebieden, aangezien dit een goede oplossing voor algemeen gebruik is. Als u verwacht geavanceerdere grafiekalgoritmen nodig te hebben, is de NetworkX-bibliotheek vaak een goede keuze.