Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Apprendre Implémentation de Graphe | Graphes
Aperçu des Algorithmes et des Structures de Données

book
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
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
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
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 []
question mark

Qu'est-ce qu'une matrice d'adjacence ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 2

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

some-alt