Cet article présente une approche pour identifier et lister toutes les composantes connexes d'un graphe non orienté en utilisant deux algorithmes de parcours fondamentaux : le parcours en profondeur (DFS) et le parcours en largeur (BFS).
Description du Problème
Étant donné un graphe non orienté composé de N sommets et E arêtes, le but est d'énumérer toutes ses composantes connexes. Les sommets sont numérotés de 0 à N-1. Lors de l'exploration d'une composante, il est stipulé de toujours démarrer depuis le sommet ayant le plus petit identifiant et de visiter les voisins par ordre croissant de leurs identifiants.
Format d'Entrée
La première ligne contient deux entiers : N (le nombre de sommets, N ≥ 0) et E (le nombre d'arêtes). Les E lignes suivantes décrivent chaque arête, spécifiant les deux sommets qu'elle relie. Les nombres sur chaque ligne sont séparés par un espace.
Format de Sortie
Chaque composante connexe doit être imprimée sur une nouvelle ligne, formatée comme suit : { v1 v2 ... vk }. L'ordre de sortie des composantes doit d'abord montrer les résultats du parcours DFS, suivis des résultats du parcours BFS.
Exemple d'Entrée
8 6
0 7
0 1
2 0
4 1
2 4
3 5
Exemple de Sortie
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
Analyse et Implémentation
Le problème met en évidence la nécessité d'implémenter les traversées DFS et BFS sur un graphe. Une considération clé est la gestion des sommets isolés ou des composantes non connectées. Pour ce faire, le programme doit itérer sur tous les sommets, et si un sommet n'a pas encore été visité, il initie un nouveau parcours à partir de ce sommet pour découvrir sa composante connexe. L'algorithme DFS est typiquement implémenté récursivement, tandis que BFS utilise une file d'attente.
Structures de Données du Graphe
Un graphe peut être représenté par une matrice d'adjacence. Les structures C suivantes définissent le graphe et ses arêtes.
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100 // Capacité maximale du graphe
// Structure pour représenter une arête
typedef struct EdgeNode {
int vertex1, vertex2;
} EdgeNode;
// Structure pour représenter le graphe (matrice d'adjacence)
typedef struct GraphNode {
int numVertices;
int numEdges;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} GraphNode;
// Fonction pour initialiser un graphe vide
GraphNode* createGraph(int vertexCount) {
GraphNode* graph = (GraphNode*)malloc(sizeof(GraphNode));
if (graph == NULL) {
perror("Échec de l'allocation mémoire pour le graphe");
exit(EXIT_FAILURE);
}
graph->numVertices = vertexCount;
graph->numEdges = 0;
// Initialiser la matrice d'adjacence à 0
for (int i = 0; i < vertexCount; ++i) {
for (int j = 0; j < vertexCount; ++j) {
graph->adjMatrix[i][j] = 0;
}
}
return graph;
}
// Fonction pour ajouter une arête au graphe (graphe non orienté)
void addEdge(EdgeNode* edge, GraphNode* graph) {
graph->adjMatrix[edge->vertex1][edge->vertex2] = 1;
graph->adjMatrix[edge->vertex2][edge->vertex1] = 1;
}
// Fonction pour construire le graphe à partir de l'entrée utilisateur
GraphNode* buildGraphFromInput() {
int n_vertices, n_edges;
printf("Entrez le nombre de sommets et d'arêtes : ");
scanf("%d %d", &n_vertices, &n_edges);
GraphNode* graph = createGraph(n_vertices);
graph->numEdges = n_edges; // Stocker le nombre d'arêtes
printf("Entrez les arêtes (paire de sommets) :\n");
for (int i = 0; i < n_edges; ++i) {
EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));
if (edge == NULL) {
perror("Échec de l'allocation mémoire pour l'arête");
exit(EXIT_FAILURE);
}
int u, v;
scanf("%d %d", &u, &v);
edge->vertex1 = u;
edge->vertex2 = v;
addEdge(edge, graph);
free(edge); // Libérer la mémoire allouée pour l'arête après usage
}
return graph;
}
// Vérifie s'il existe une arête entre deux sommets
int hasEdge(GraphNode* graph, int u, int v) {
return graph->adjMatrix[u][v] == 1;
}
// Tableau global pour suivre les sommets visités
int visited[MAX_VERTICES];
// Initialise le tableau des sommets visités
void initializeVisited() {
for (int i = 0; i < MAX_VERTICES; ++i) {
visited[i] = 0;
}
}
// Algorithme de parcours en profondeur (DFS)
void performDFS(GraphNode* graph, int currentVertex) {
printf("%d ", currentVertex);
visited[currentVertex] = 1; // Marquer le sommet comme visité
// Parcourir les voisins
for (int neighbor = 0; neighbor < graph->numVertices; ++neighbor) {
if (!visited[neighbor] && hasEdge(graph, currentVertex, neighbor)) {
performDFS(graph, neighbor);
}
}
}
// Implémentation d'une file d'attente simple pour BFS
#define QUEUE_CAPACITY 100 // Capacité de la file d'attente
int bfsQueue[QUEUE_CAPACITY];
int queueFront = 0;
int queueRear = -1;
int queueSize = 0;
// Ajoute un élément à la fin de la file
void enqueue(int value) {
if (queueSize >= QUEUE_CAPACITY) {
printf("Erreur: File d'attente pleine.\n");
return;
}
queueRear = (queueRear + 1) % QUEUE_CAPACITY;
bfsQueue[queueRear] = value;
queueSize++;
}
// Retire et retourne l'élément du début de la file
int dequeue() {
if (queueSize == 0) {
printf("Erreur: File d'attente vide.\n");
return -1; // Valeur d'erreur
}
int value = bfsQueue[queueFront];
queueFront = (queueFront + 1) % QUEUE_CAPACITY;
queueSize--;
return value;
}
// Vérifie si la file est vide
int isQueueEmpty() {
return queueSize == 0;
}
// Algorithme de parcours en largeur (BFS)
void performBFS(GraphNode* graph, int startVertex) {
enqueue(startVertex);
visited[startVertex] = 1; // Marquer le sommet comme visité
while (!isQueueEmpty()) {
int currentVertex = dequeue();
printf("%d ", currentVertex);
// Parcourir les voisins
for (int neighbor = 0; neighbor < graph->numVertices; ++neighbor) {
if (!visited[neighbor] && hasEdge(graph, currentVertex, neighbor)) {
enqueue(neighbor);
visited[neighbor] = 1; // Marquer le voisin comme visité lors de l'ajout à la file
}
}
}
}
int main() {
GraphNode* graph = buildGraphFromInput();
// Affichage des composantes connexes par DFS
initializeVisited(); // Réinitialiser le marquage des sommets visités
printf("Composantes connexes (DFS) :\n");
for (int i = 0; i < graph->numVertices; ++i) {
if (!visited[i]) {
printf("{ ");
performDFS(graph, i);
printf("}\n");
}
}
// Affichage des composantes connexes par BFS
initializeVisited(); // Réinitialiser le marquage des sommets visités pour BFS
printf("Composantes connexes (BFS) :\n");
for (int i = 0; i < graph->numVertices; ++i) {
if (!visited[i]) {
printf("{ ");
performBFS(graph, i);
printf("}\n");
}
}
// Libérer la mémoire allouée pour le graphe
free(graph);
return 0;
}
Logique Principale
Le programme principal itère sur tous les sommets de 0 à N-1. Pour chaque sommet, il vérifie s'il a déjà été visité. Si ce n'est pas le cas, cela indique le début d'une nouvelle composante connexe. Un parcours (DFS ou BFS) est alors lancé à partir de ce sommet pour explorer et imprimer tous les sommets de cette composante. Après avoir traité toutes les composantes avec DFS, le processus est répété pour BFS, en réinitialisant d'abord le tableau des visites.