Nun werden wir 3 Arten der Graphimplementierung in Python betrachten.

Implementierung mit der graphviz-Bibliothek

Graphviz ist eine leistungsstarke Bibliothek zum Erstellen und Visualisieren von Graphen. Sie bietet eine einfache und intuitive Schnittstelle zur Erstellung von Graphvisualisierungen, was sie ideal für die Darstellung komplexer Graphstrukturen macht.

import graphviz

class Graph:
    def __init__(self):
        self.graph = graphviz.Graph()

    def add_vertex(self, vertex):
        self.graph.node(str(vertex))

    def add_edge(self, from_vertex, to_vertex):
        self.graph.edge(str(from_vertex), str(to_vertex))

    def get_neighbors(self, vertex):
        neighbors = []
        for edge in self.graph.body:
            if edge.startswith(f'{vertex}" ->'):
                neighbor = edge.split('-> ')[1].split(' [')[0]
                neighbors.append(neighbor)
        return neighbors

Implementierung mit Adjazenzmatrix

Eine Adjazenzmatrix ist eine quadratische Matrix, die verwendet wird, um einen Graphen darzustellen. In dieser Matrix entsprechen die Zeilen und Spalten den Knoten (oder Knotenpunkten) im Graphen, und das Vorhandensein oder Fehlen von Kanten zwischen den Knoten wird durch die Werte der Matrixelemente dargestellt.
Diese Implementierung bietet eine kompakte und effiziente Darstellung von Graphdaten, insbesondere für dichte Graphen mit vielen Verbindungen.

Hinweis

In einem gewichteten Graphen können die Werte in der Adjazenzmatrix die Gewichte der Kanten darstellen. Der Matrixwert kann entweder null oder unendlich sein, wenn keine Kante zwischen den Knoten vorhanden ist.

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = np.zeros((size, size), dtype=int)

    def add_edge(self, from_vertex, to_vertex):
        self.matrix[from_vertex][to_vertex] = 1
        self.matrix[to_vertex][from_vertex] = 1

    def add_vertex(self):
        self.size += 1
        new_matrix = np.zeros((self.size, self.size), dtype=int)
        new_matrix[:self.size-1, :self.size-1] = self.matrix
        self.matrix = new_matrix

    def find_neighbors(self, vertex):
        neighbors = []
        for i in range(self.size):
            if self.matrix[vertex][i] == 1:
                neighbors.append(i)
        return neighbors

Implementierung mit Python-Dictionary

Die Implementierung eines Graphen mit einem Dictionary ist ein beliebter Ansatz in Python. In dieser Implementierung repräsentieren die Schlüssel des Dictionaries die Knoten (oder Knotenpunkte) des Graphen, und die Werte repräsentieren die Nachbarn (oder angrenzenden Knoten) jedes Knotens. Dies ermöglicht einen effizienten Zugriff auf die Nachbarn eines gegebenen Knotens.

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, from_vertex, to_vertex):
        if from_vertex in self.graph and to_vertex in self.graph:
            self.graph[from_vertex].append(to_vertex)
            self.graph[to_vertex].append(from_vertex)  # For undirected graph

    def get_neighbors(self, vertex):
        if vertex in self.graph:
            return self.graph[vertex]
        else:
            return []