Vérifier si un graphe donné est connecté ou non - solution en python

Le problème

Un graphe \(G=(S,A)\) est dit connecté, si pour tout couple de sommets \((u,v)\) il existe un chemin reliant \(u\) et \(v\)

Exemple 1 : graphe orienté

Graphe orienté connecté

Le graphe ci-dessus est connecté parce que nous pouvons trouver un chemin entre chaque couple de sommets.
Les couples de sommets sont : (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,2), (3,4), (3,5), (4,5)

Exemple 2 : graphe non orienté

Graphe non orienté non connecté

Le graphe ci-dessus n'est pas connecté car nous ne pouvons pas trouver de chemin entre les sommets (5,6) et les autres sommets.
Ce graphe est composé de deux composants connectés.

Question

Écrivez une fonction qui permet de vérifier si un graphe donné est connecté ou non.

Remarque Le graphe est représenté en utilisant la matrice d'adjacence.

Solution

Pour résoudre ce problème, je vais décomposer le problème en deux sous-problèmes :

Vérifier d'abord s'il existe un chemin entre deux sommets
Ensuite, la fonction principale, pour chaque couple de sommets, vérifie s'il existe un chemin entre eux

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SOMMETS 100

// Fonction pour vérifier s'il existe un chemin entre deux sommets (BFS)
bool existeChemin(int matriceAdj[MAX_SOMMETS][MAX_SOMMETS], int n, int u, int v) {
    // File d'attente pour le BFS
    int file[MAX_SOMMETS];
    int debut = 0, fin = 0;
    
    // Tableau des sommets visités
    bool visites[MAX_SOMMETS] = {false};
    
    // Ajouter le premier sommet à la file
    file[fin++] = u;
    visites[u] = true;
    
    while (debut < fin) {
        // Supprimer le sommet en tête de file
        int courant = file[debut++];
        
        // Parcourir tous les sommets adjacents
        for (int i = 0; i < n; i++) {
            if (matriceAdj[courant][i] > 0) {
                // Si le sommet i est la destination, chemin trouvé
                if (i == v) {
                    return true;
                }
                
                // Si le sommet n'a pas été visité, l'ajouter à la file
                if (!visites[i]) {
                    file[fin++] = i;
                    visites[i] = true;
                }
            }
        }
    }
    
    return false;
}

// Fonction pour vérifier si un graphe non orienté est connecté
bool estConnecteNonOriente(int matriceAdj[MAX_SOMMETS][MAX_SOMMETS], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!existeChemin(matriceAdj, n, i, j)) {
                return false;
            }
        }
    }
    return true;
}

// Fonction pour vérifier si un graphe orienté est connecté
bool estConnecteOriente(int matriceAdj[MAX_SOMMETS][MAX_SOMMETS], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && !existeChemin(matriceAdj, n, i, j)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    // Exemple 1 : graphe orienté connecté
    int matriceOriente[MAX_SOMMETS][MAX_SOMMETS] = {
        {0, 1, 1, 1, 0},
        {0, 0, 1, 0, 1},
        {0, 0, 0, 1, 1},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0}
    };
    int n1 = 5;
    
    printf("Test graphe orienté : ");
    if (estConnecteOriente(matriceOriente, n1)) {
        printf("Connecté\n");
    } else {
        printf("Non connecté\n");
    }
    
    // Exemple 2 : graphe non orienté non connecté
    int matriceNonOriente[MAX_SOMMETS][MAX_SOMMETS] = {
        {0, 1, 1, 1, 0, 0},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 0, 0},
        {1, 1, 1, 0, 0, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 1, 0}
    };
    int n2 = 6;
    
    printf("Test graphe non orienté : ");
    if (estConnecteNonOriente(matriceNonOriente, n2)) {
        printf("Connecté\n");
    } else {
        printf("Non connecté\n");
    }
    
    return 0;
}

Sortie

Test graphe orienté : Connecté
Test graphe non orienté : Non connecté

Vérifier s'il existe un chemin entre deux sommets

# Cette fonction utilise un algorithme de parcours en largeur
# pour savoir s'il existe un chemin entre deux sommets
# le graphe est représenté par la matrice d'adjacence
def ExistChemin(matriceAdj, u, v):
    n = len(matriceAdj)  # nombre de sommets dans le graphe
    file = []
    visites = [False] * n
    # ajouter le premier sommet à la file d'attente
    file.append(u)
    while file:
        # supprimer le sommet supérieur de la pile et marqué comme visité
        courant = file.pop(0)
        visites[courant] = True

        # visiter les sommets adjacents
        for i in range(n):
            # s'il existe et qu'un bord entre u et i et
            # le sommet i n'est pas encore visité
            if matriceAdj[courant][i] > 0 and visites[i] == False:
                # ajouter i à la file marqué comme visité
                file.append(i)
                visites[i] = True

            # Si le sommet i est le sommet voulu (i = v)
            # donc il existe un chemin de u à i(v)
            elif matriceAdj[courant][i] > 0 and i == v:
                return True

    return False

Fonction principale - cas graphe non orienté

def connecte(matriceAdj):
    n = len(matriceAdj)  # nombre de sommets
    for i in range(n):
        for j in range(i+1, n):
            if ExistChemin(matriceAdj, i, j) == False:
                return False
    return True

Fonction principale - cas graphe orienté

def connecte(matriceAdj):
    n = len(matriceAdj)  # nombre de sommets
    for i in range(n):
        for j in range(n):
            if i != j and ExistChemin(matriceAdj, i, j) == False:
                return False
    return True

Test des fonctions

Tests Python

# Exemple 1 : graphe orienté connecté
graphe_oriente = [
    [0, 1, 1, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]
]

print("Test graphe orienté :", "Connecté" if connecte(graphe_oriente) else "Non connecté")

# Exemple 2 : graphe non orienté non connecté
graphe_non_oriente = [
    [0, 1, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 0],
    [1, 1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0]
]

print("Test graphe non orienté :", "Connecté" if connecte(graphe_non_oriente) else "Non connecté")

Sortie

Test graphe orienté : Connecté
Test graphe non orienté : Non connecté

Explication de l'algorithme

Parcours en largeur (BFS) :

On utilise une file d'attente pour explorer le graphe niveau par niveau à partir du sommet u.
On marque les sommets visités pour éviter les cycles.
Si on atteint le sommet v, alors il existe un chemin de u à v.

Complexité :

Temps : \(O(n^3)\) dans le pire cas (pour chaque paire, on fait un BFS en \(O(n^2)\)).
Espace : \(O(n^2)\) pour la matrice d'adjacence, plus \(O(n)\) pour la file et les marques.

Amélioration possible

On peut optimiser en utilisant un seul BFS/DFS à partir d'un sommet quelconque. Si tous les sommets sont visités, le graphe est connecté (pour les graphes non orientés).

def estConnecteOptimise(matriceAdj):
    n = len(matriceAdj)
    visites = [False] * n
    file = [0]  # Commencer par le sommet 0
    visites[0] = True
    
    while file:
        courant = file.pop(0)
        for i in range(n):
            if matriceAdj[courant][i] > 0 and not visites[i]:
                file.append(i)
                visites[i] = True
    
    # Vérifier si tous les sommets ont été visités
    return all(visites)

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Précédent Parcours en largeur d'un arbre binaire

Vérifier si un graphe donné est connecté ou non - solution en python

Le problème

Exemple 1 : graphe orienté

Exemple 2 : graphe non orienté

Question

Solution

Vérifier s'il existe un chemin entre deux sommets

Fonction principale - cas graphe non orienté

Fonction principale - cas graphe orienté

Test des fonctions

Amélioration possible

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Vérifier si un graphe donné est connecté ou non - solution en python

Le problème

Exemple 1 : graphe orienté

Exemple 2 : graphe non orienté

Question

Solution

Vérifier s'il existe un chemin entre deux sommets

Fonction principale - cas graphe non orienté

Fonction principale - cas graphe orienté

Test des fonctions

Amélioration possible

Discussion (0)

Laisser un commentaire