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

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é

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é

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

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

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

• Vérifiez d'abord s'il existe un chemin entre deux sommets
• Deuxièmement, la fonction principale, pour chaque couple de sommets, vérifiez s'il existe un chemin entre eux

Vérifiez d'abord 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

                            

La fonction principale - cas graphe non orienté

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

    return True
                            

La fonction principale - cas graphe orienté

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

    return True