Implémentation de Graphe

Nous allons maintenant examiner 3 types d'implémentation de graphes en Python.

Implémentation en utilisant la bibliothèque graphviz

Graphviz est une bibliothèque puissante pour créer et visualiser des graphes. Elle fournit une interface simple et intuitive pour générer des visualisations de graphes, ce qui la rend idéale pour afficher des structures de graphes complexes.

python
Copier le code
Collapse
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

Implémentation à l'aide d'une matrice d'adjacence

Une matrice d'adjacence est une matrice carrée utilisée pour représenter un graphe. Dans cette matrice, les lignes et les colonnes correspondent aux sommets (ou nœuds) du graphe, et la présence ou l'absence d'arêtes entre les sommets est représentée par les valeurs des éléments de la matrice.
Cette implémentation offre une représentation compacte et efficace des données du graphe, en particulier pour les graphes denses avec de nombreuses connexions.

Remarque

Dans un graphe pondéré, les valeurs de la matrice d'adjacence peuvent représenter les poids des arêtes. La valeur de la matrice peut être soit zéro, soit l'infini lorsqu'il n'y a pas d'arête entre les sommets.

python
Copier le code
Collapse
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

Implémentation en utilisant un dictionnaire Python

L'implémentation de graphes en utilisant un dictionnaire est une approche populaire en Python. Dans cette implémentation, les clés du dictionnaire représentent les sommets (ou nœuds) du graphe, et les valeurs représentent les voisins (ou sommets adjacents) de chaque sommet. Cela permet un accès efficace aux voisins d'un sommet donné.

python
Copier le code
Collapse
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 []