Structures de données - Graphe
Un graphe est une structure de données non linéaire plus générale utilisée pour représenter des relations complexes « plusieurs à plusieurs » entre éléments, composée de sommets et d'arêtes reliant les sommets.
Concepts de base des graphes
Types de graphesTypes de graphes — Graphe non orienté, Graphe orienté, Graphe pondéré
Graphe non orienté
0
—1
Les arêtes n'ont pas de direction ; les connexions sont réciproques.
Exemple : relations d'amitié dans un réseau social
Exemple : relations d'amitié dans un réseau social
Graphe orienté
0
→1
Les arêtes ont une direction ; les connexions sont unidirectionnelles.
Exemple : relations d'abonnement, liens entre pages web
Exemple : relations d'abonnement, liens entre pages web
Graphe pondéré
0
51
Les arêtes portent des poids (distance/coût)
Exemple : navigation cartographique, latence réseau
Exemple : navigation cartographique, latence réseau
Méthodes de stockage des graphes
Comparaison des méthodes de stockageMatrice d'adjacence vs liste d'adjacence
Matrice d'adjacence
Complexité spatialeO(V²)
Vérifier si deux sommets sont connectésO(1)
Parcourir les sommets adjacentsO(V)
Adapté pour : graphes denses · int graph[V][V]
Liste d'adjacence
Complexité spatialeO(V+E)
Vérifier si deux sommets sont connectésO(degree)
Parcourir les sommets adjacentsO(degree)
Adapté pour : graphes creux · Tableau de listes chaînées
Parcours de graphe
DFS vs BFS — Parcours à partir du sommet 0
DFS en profondeur
0→
1→
3→
4→
2→
5
Parcourir un chemin jusqu'au bout, puis revenir en arrière
Implémentation : récursion / pile | Adapté à la recherche de chemin, au tri topologique
BFS en largeur
0→
1→
2→
3→
4→
5
Explorer niveau par niveau ; les nœuds d'un même niveau sont visités en premier
Implémentation : file | Naturellement adapté aux plus courts chemins dans les graphes non pondérés
Exemples
#include <stdio.h>
#include <stdbool.h>
#define V 6 /* nombre de sommets */
/* Graphe représenté par une matrice d'adjacence */
int graph[V][V] = {
{0,1,1,0,0,0}, /* Relations d'adjacence du sommet 0 */
{1,0,0,1,1,0}, /* Sommet 1 */
{1,0,0,0,1,0}, /* Sommet 2 */
{0,1,0,0,0,1}, /* Sommet 3 */
{0,1,1,0,0,1}, /* Sommet 4 */
{0,0,0,1,1,0} /* Sommet 5 */
};
bool visited[V];
/* DFS : parcours en profondeur, implémentation récursive Caractéristiques : suit un chemin jusqu'au bout et revient en arrière, adapté à la recherche de chemin et à la vérification de connectivité */
/* Visiter le sommet courant */
void DFS(int v) {
visited[v] = true;
printf("%d ", v); /* Visiter récursivement les sommets adjacents non visités */
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i); /* BFS : parcours en largeur, implémenté à l'aide d'une file Caractéristiques : se déploie couche par couche, naturellement adapté à la recherche des plus courts chemins */
}
}
}
/* Enfiler le sommet de départ */
/* Défiler */
void BFS(int start) {
bool visited[V] = {false};
int queue[V];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start; /* Enfiler les sommets adjacents */
while (front < rear) {
int v = queue[front++]; /* Initialiser les indicateurs de visite */
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i; "DFS (à partir du sommet 0) : "
}
}
}
}
int main() {
/* Sortie : 0 1 3 5 4 2 */
for (int i = 0; i < V; i++) visited[i] = false;
printf("BFS (à partir du sommet 0): ");
DFS(0); /* Sortie: 0 1 2 3 4 5 */
printf("\n");
printf(Scénarios d'application des graphes);
BFS(0); Scénarios
printf("\n");
return 0;
}
#include <stdbool.h>
#define V 6 /* nombre de sommets */
/* Graphe représenté par une matrice d'adjacence */
int graph[V][V] = {
{0,1,1,0,0,0}, /* Relations d'adjacence du sommet 0 */
{1,0,0,1,1,0}, /* Sommet 1 */
{1,0,0,0,1,0}, /* Sommet 2 */
{0,1,0,0,0,1}, /* Sommet 3 */
{0,1,1,0,0,1}, /* Sommet 4 */
{0,0,0,1,1,0} /* Sommet 5 */
};
bool visited[V];
/* DFS : parcours en profondeur, implémentation récursive Caractéristiques : suit un chemin jusqu'au bout et revient en arrière, adapté à la recherche de chemin et à la vérification de connectivité */
/* Visiter le sommet courant */
void DFS(int v) {
visited[v] = true;
printf("%d ", v); /* Visiter récursivement les sommets adjacents non visités */
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i); /* BFS : parcours en largeur, implémenté à l'aide d'une file Caractéristiques : se déploie couche par couche, naturellement adapté à la recherche des plus courts chemins */
}
}
}
/* Enfiler le sommet de départ */
/* Défiler */
void BFS(int start) {
bool visited[V] = {false};
int queue[V];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start; /* Enfiler les sommets adjacents */
while (front < rear) {
int v = queue[front++]; /* Initialiser les indicateurs de visite */
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i; "DFS (à partir du sommet 0) : "
}
}
}
}
int main() {
/* Sortie : 0 1 3 5 4 2 */
for (int i = 0; i < V; i++) visited[i] = false;
printf("BFS (à partir du sommet 0): ");
DFS(0); /* Sortie: 0 1 2 3 4 5 */
printf("\n");
printf(Scénarios d'application des graphes);
BFS(0); Scénarios
printf("\n");
return 0;
}
Scénarios d'application des graphes
| Plus court chemin | Dijkstra, Bellman-Ford (navigation cartographique) |
|---|---|
| Arbre couvrant minimal | Prim, Kruskal (optimisation du câblage réseau) |
| Tri topologique | Algorithme de Kahn (analyse des dépendances entre tâches) |
| Analyse des réseaux sociaux | PageRank, détection de communautés |
| Autres extensions | Réflexion de l'IA... |