Structure de la théorie des graphes
En informatique, les graphes sont largement utilisés pour modéliser les réseaux sociaux (les utilisateurs sont des nœuds, les amitiés sont des arêtes), les liens web (les pages web sont des nœuds, les hyperliens sont des arêtes), les réseaux de communication, et même les problèmes de planification de trajets.
GrapheC'est comme un graphe de relations de réseau social :
- Nœud (Sommet): Chaque personne dans le réseau social
- Arête: Relations entre les personnes (amis, abonnements, etc.)
- Poids: force de la relation (proximité, fréquence d'interaction, etc.)
Imaginez le réseau de transport de votre ville : divers lieux (comme la maison, l'école, le centre commercial) sontPoint, les routes reliant ces lieux sontLigne. Un graphe (Graph) est l'abstraction mathématique de la relation entre les points et les lignes ; il est utilisé pour représenterRelations complexes entre entitésune structure de données.
Exemples concrets :
- Carte: les villes sont des nœuds, les routes sont des arêtes, les distances sont des poids
- Circuit: les composants sont des nœuds, les fils sont des arêtes, la résistance est le poids
- Internet: les sites web sont des nœuds, les liens sont des arêtes, le trafic est le poids
- Réseau de transport: les stations sont des nœuds, les itinéraires sont des arêtes, les tarifs sont les poids
| Scénarios | Autres structures | Structure de graphe |
|---|---|---|
| Relations sociales | Difficile d'exprimer des relations complexes | Exprime naturellement les relations plusieurs-à-plusieurs |
| Planification de chemin | Nécessite des structures de données complexes | Représente intuitivement les réseaux et les chemins |
| Relations de dépendance | Difficile de représenter les dépendances circulaires | Gère facilement les dépendances complexes |
| Analyse de réseau | Ne peut pas exprimer la topologie du réseau | Décrit parfaitement la structure du réseau |
Terminologie de base des graphes
| Terme | définition | Analogie avec la vie | Représentation symbolique |
|---|---|---|---|
| Sommet | Unité de base dans un graphe | Personnes dans les réseaux sociaux | V, u, v |
| Edge | Une ligne reliant deux sommets | Relation entre deux personnes | E, (u,v) |
| Degré | Nombre d'arêtes connectées à un sommet | Nombre d'amis d'une personne | deg(v) |
| Chemin | Séquence de sommets | Chemin de A à B | v₁→v₂→…→vₙ |
| Cycle | Un chemin avec le même point de départ et d'arrivée | Partir de chez soi et y revenir finalement | v₁→v₂→…→v₁ |
| Graphe connexe | Il existe un chemin entre deux points quelconques | Chacun peut se connecter avec les autres | |
| Poids | Propriété numérique d'une arête | Distance entre deux villes | w(u,v) |
Classification des graphes

| Critères de classification | Type | Fonctionnalités | scénarios d'application |
|---|---|---|---|
| Orientation | Graphe non orienté | Les arêtes n'ont pas de direction | Relations d'amitié, réseaux routiers |
| Graphe orienté | Les arêtes ont une direction | Relations de suivi, flux de travail | |
| Poids | Graphe non pondéré | Toutes les arêtes ont le même poids | Relations de réseaux sociaux |
| Graphe pondéré | Les arêtes ont des poids différents | Distance sur une carte, trafic réseau | |
| Connectivité | Graphe connexe | Deux points quelconques sont accessibles | Réseau de transport |
| Graphe non connexe | Il y a des sommets isolés | Groupes sociaux | |
| Cycle | Graphe acyclique | Aucun cycle | Dépendances des tâches, arborescences de fichiers |
| Graphe cyclique | Cycles | Carte routière |
Méthodes de représentation des graphes
matrice d'adjacence
| Fonctionnalités | Description | Complexité temporelle | Complexité spatiale |
|---|---|---|---|
| Méthode de stockage | matrice bidimensionnelle | ||
| vérifier l'existence d'une arête | matrix[i][j] != 0 |
O(1) | |
| arête | matrix[i][j] = weight |
O(1) | |
| supprimer une arête | matrix[i][j] = 0 |
O(1) | |
| parcourir les sommets adjacents | parcourir une ligne/colonne | O(V) | |
| utilisation de l'espace | matrice V×V | O(V²) |
liste d'adjacence
| Fonctionnalités | Description | Complexité temporelle | Complexité spatiale |
|---|---|---|---|
| Méthode de stockage | tableau + liste chaînée | ||
| vérifier l'existence d'une arête | Recherche dans une liste chaînée | O(deg(v)) | |
| arête | Ajout dans une liste chaînée | O(1) | |
| supprimer une arête | Suppression dans une liste chaînée | O(deg(v)) | |
| parcourir les sommets adjacents | parcourir une liste chaînée | O(deg(v)) | |
| utilisation de l'espace | Tableau de sommets + liste chaînée d'arêtes | O(V+E) |
Concepts de base des graphes
un grapheGSe compose de deux ensembles :
- Ensemble de sommets V (Ensemble de sommets): L'ensemble de tous les sommets du graphe.
- Ensemble d'arêtes E (Ensemble d'arêtes): l'ensemble des lignes reliant ces points. Une arête est définie par les deux sommets qu'elle relie
(u, v)Représente.
Exemple
# Sommets : Alice, Bob, Charlie, Diana
# Arêtes : représentent les relations d'amitié entre eux
social_graph = {
'Alice': ['Bob', 'Charlie'], # Alice est amie avec Bob et Charlie
'Bob': ['Alice', 'Charlie', 'Diana'],
'Charlie': ['Alice', 'Bob'],
'Diana': ['Bob']
}
print(fSommets (utilisateurs) : {list(social_graph.keys())})
print(fAmis d'Alice (arêtes) : {social_graph['Alice']})
Sortie :
顶点(用户): ['Alice', 'Bob', 'Charlie', 'Diana'] Alice 的好友(边): ['Bob', 'Charlie']
Classification des graphes et concepts importants
Les graphes peuvent être divisés en plusieurs types selon les propriétés de leurs arêtes ; leur compréhension est la base de la maîtrise de la théorie des graphes.
Graphe non orienté vs graphe orienté
| Type | Caractéristiques des arêtes (arête) | analogie avec la vie | Exemple |
|---|---|---|---|
| Graphe non orienté | Les arêtes n'ont pas de direction,(A, B)Représente que A et B sont mutuellement connectés. |
amitié bidirectionnelle: si Alice est l'amie de Bob, alors Bob doit aussi être l'ami d'Alice. | Amitiés dans les réseaux sociaux, connexions dans les circuits. |
| Graphe orienté | les arêtes ont une direction,A -> BReprésente une connexion à sens unique de A à B. |
Suivi sur Weibo: Vous pouvez suivre quelqu'un, mais l'autre personne peut ne pas vous suivre en retour. | Hyperliens web, dépendances entre tâches, routes à sens unique. |

graphe pondéré
Dans un graphe pondéré, une valeur numérique (poids) est attribuée à chaque arête, ce qui peut représenter une distance, un coût, un temps ou la force d'une relation.
Exemple
weighted_graph = {
'Beijing': {('Shanghai', 1200), ('Tianjin', 100)}, # La distance de Beijing à Shanghai est de 1200, à Tianjin de 100
'Shanghai': {('Pékin', 1200), ('Hangzhou', 200)},
'Tianjin': {('Pékin', 100)},
'Hangzhou': {('Shanghai', 200)}
}
termes clés
- degré (Degree): le nombre d'arêtes connectées à un sommet. Dans un graphe orienté, il est divisé endegré entrant(nombre d'arêtes pointant vers le sommet) etdegré sortant(nombre d'arêtes partant du sommet).
- chemin (Path): une séquence d'arêtes parcourues d'un sommet à un autre. Par exemple,
A -> B -> C。 - cycle/circuit (Cycle): un chemin dont le point de départ et le point d'arrivée sont le même sommet.
- graphe connexe: dans un graphe non orienté, il existe un chemin entre deux sommets quelconques.
- graphe fortement connexe: dans un graphe orienté, il existe un chemin entre deux sommets quelconques.chemin bidirectionnel.
Méthodes de stockage des graphes
Comment représenter un graphe dans un ordinateur ? Il existe principalement deux méthodes courantes.
matrice d'adjacence
Utiliser un tableau à deux dimensions (matrice)matrixpour représenter le graphe.matrix[i][j]La valeur représente le sommetivers le sommetjLa situation des arêtes.
- Pour les graphes non orientés, la matrice est symétrique.
- Pour un graphe pondéré, les entrées de la matrice stockent les poids (en utilisant des valeurs spéciales telles que
0ou∞Représente l'absence d'arête). - Avantages: vérifier s'il existe une arête entre deux sommets quelconques est très rapide (
O(1))。 - Inconvénients: prend beaucoup d'espace (
O(V^2)), mais il gaspille de l'espace pour les « graphes creux » avec peu d'arêtes.
Exemple
# Sommets : 0-A, 1-B, 2-C
# Arêtes : A-B, A-C
V = 3 # Nombre de sommets
adj_matrix = [[0] * V for _ in range(V)]
# Ajouter une arête A-B (0-1)
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1 # Un graphe non orienté doit définir des positions symétriques
# Ajouter une arête A-C (0-2)
adj_matrix[0][2] = 1
adj_matrix[2][0] = 1
print("Matrice d'adjacence :")
for row in adj_matrix:
print(row)
# Sortie :
# [0, 1, 1]
# [1, 0, 0]
# [1, 0, 0]
liste d'adjacence
Maintenir une liste (liste chaînée, tableau, etc.) pour chaque sommet, enregistrant tous les sommets (et les poids) directement connectés à celui-ci.
- Avantages: Haute efficacité spatiale (
O(V + E)), particulièrement adapté aux graphes creux. Il peut trouver rapidement tous les voisins d'un sommet. - Inconvénients: vérifier s'il existe une arête entre deux sommets quelconques est plus lent (
O(degree(V)))。
Exemple
adj_list = {
'A': ['B', 'C'], # A est relié à B et C
'B': ['A'], # B est relié à A
'C': ['A'] # C est relié à A
}
print("Liste d'adjacence :")
for vertex, neighbors in adj_list.items():
print(f"{vertex} : {neighbors}")
Algorithmes de parcours de graphes
Le parcours est la base des algorithmes de graphes ; il consiste à visiter systématiquement chaque sommet du graphe.
Il existe principalement deux stratégies :
Parcours en largeur
Le parcours en largeur (BFS) est comme une « diffusion d'onde » : à partir du point de départ, il visite d'abord tous les voisins directs, puis les voisins des voisins, et ainsi de suite. Il utilise unefilepour l'implémenter.
Étapes de l'algorithme:
- Mettre le point de départ dans une file et le marquer comme visité.
- Lorsque la file n'est pas vide :
a. Retirer le sommet en tête de la file
v. b. Visitervtous ses voisins non visités, les mettre dans la file et les marquer comme visités. - Répéter l'étape 2.
Exemple
def bfs(graph, start):
"""Utiliser BFS pour parcourir le graphe, renvoyer l'ordre de visite"""
visited = set([start]) # Enregistrer les sommets visités
queue = deque([start]) # Initialiser la file
result = [] # Enregistrer l'ordre de visite
while queue:
vertex = queue.popleft()
result.append(vertex)
# Parcourir les voisins du sommet actuel
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# Données de test
test_graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("Ordre de parcours BFS (à partir de A) :", bfs(test_graph, 'A'))
# La sortie pourrait être : ['A', 'B', 'C', 'D', 'E', 'F']
Recherche en profondeur
La recherche en profondeur (DFS) est comme "se promener dans un labyrinthe" : elle choisit un chemin, va jusqu'au bout, puis revient en arrière et prend un autre chemin. Elle utilisePile(ou la récursion) pour l'implémenter.
Étapes de l'algorithme récursif:
- du sommet
vStart, marquer comme visité. - for
vchaque voisin non visité deu: a. Appel récursifDFS(u)。
Exemple
"""Implémenter DFS en utilisant la récursion"""
if visited is None:
visited = set()
if result is None:
result = []
visited.add(vertex)
result.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, result)
return result
print("Ordre de parcours DFS (en partant de A) :", dfs_recursive(test_graph, 'A'))
# La sortie peut être : ['A', 'B', 'D', 'E', 'F', 'C']
Comparaison des algorithmes de parcours de graphe :

Scénarios d'application classiques et introduction aux algorithmes
Une fois que vous maîtrisez la représentation et le parcours des graphes, vous pouvez explorer de nombreux problèmes classiques :
Problème du plus court chemin: dans la navigation cartographique, trouver la distance de conduite la plus courte entre deux points.
- Algorithme de Dijkstra: s'applique auxgraphes à poids non négatifs.
- Algorithme de Floyd: calculer les plus courts chemins entre toutes les paires de sommets.
Arbre couvrant minimal: sous condition de garder tous les sommets connectés, sélectionner l'ensemble d'arêtes de poids total minimal (par exemple, déployer le réseau de fibre optique le moins coûteux pour plusieurs villages).
- Algorithme de Prim
- Algorithme de Kruskal
Tri topologique: ordonner linéairement les sommets d'un graphe orienté acyclique (DAG) de sorte que pour toute arête orientée
u->v,uDans le tri, tous sont classésvavant (par exemple, organiser l'ordre d'apprentissage des cours).