Petit problème d'algorithme2

Bonjour,

J'ai écrit ce petit programme qui modélise un graphe orienté simple :

class Graphe:
        
        def __init__(self):
                self.sommet = [] # liste initialisee a vide pour les sommets
                self.succ = []   # liste initialisee a  vide pour les successeurs

        def ajouter_sommet(self, nouv_som):
                if nouv_som in self.sommet:
                        print("Attention! Ce nom de sommet est deja dans la liste.")
                        nouv_som = str(input("Entrez un nouveau nom : "))
                        while nouv_som in self.sommet:
                                if nouv_som in self.sommet:
                                        print("Attention! Ce nom de sommet est deja dans la liste.")
                                        nouv_som = str(input("Entrez un nouveau nom : "))
                        self.sommet.append(nouv_som)
                        self.succ.append([])
                else:
                        self.sommet.append(nouv_som)
                        self.succ.append([])

        def ajouter_arc(self, ext_ini, ext_fin, a = 0, b = 0):
                if ext_ini in self.sommet and ext_fin in self.sommet:                   
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                elif ext_ini == ext_fin and ext_ini in self.sommet:
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_ini)
                elif ext_ini == ext_fin and ext_ini not in self.sommet:
                        self.sommet.append(ext_ini)
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_ini)                        
                elif ext_ini not in self.sommet and ext_fin in self.sommet:
                        self.sommet.append(ext_ini)
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                elif ext_ini in self.sommet and ext_fin not in self.sommet:
                        self.sommet.append(ext_fin)
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                else:
                        self.sommet.append(ext_ini)
                        self.sommet.append(ext_fin)
                        self.succ.append([])
                        self.succ.append([])
                        a = self.sommet.index(ext_ini)
                        b = self.sommet.index(ext_fin)
                if b in self.succ[a]:
                        print("Attention! Cette relation existe deja. Le doublon va etre enleve.")
                        self.succ[a].remove(b)
                self.succ[a].append(b)

Je souhaite ajouter une fonction de parcours en largeur (algorithme du plus court chemin). Je pense procéder de la façon suivante :

def parcours(self, G, x, Gprim) :
             queue = []
             pour chaque successeur y de x faire :
                    enfiler (x,y) dans queue
             tant que queue n'est pas vide faire :
                    (i,f) = défiler(queue)
                     si f n'a pas encore été visité alors :
                           marquer f comme "visité"
                           ajouter f dans Gprim
                           ajouter l'arc (i,f) dans Gprim
                           pour chaque successeur de y de f faire :
                                    enfiler (x,y) dans queue

En plus de l'arbre couvrant calculé par l'algorithme, je souhaite :
1. calculer une table associant à chaque sommet y la distance en nombre d'arcs entre x et y,
2. utiliser une liste pour représenter cette table. Si on note d cette liste et si l'indice du sommet y dans la liste de sommets du graphe est i, d[i] est alors la distance de x à y.
3. choisir une valeur particulière pour noter les sommets qui ne sont pas accessibles à partir de x.


Si j'ai des graphes représentant des relations entre personnes, entreprises ou objets et résultant de sondages ou de relevés d'informations publiques. Ces graphes sont anonymes si bien qu'il n'est pas possible de connaître ce qu'ils représentent (ex : le graphe des envois de courrier interne entre employés au sein d'une entreprise ...).

En utilisant les résultats de l'algorithme du plus court chemin pour fournir des informations à partir du graphe :

1. Quelle peut être la longueur maximale d'un plus court chemin entre deux sommets de graphes ?
2. Existe t'il des communautés potentielles dans la population étudiée ? On peut peut être assimiler une communauté potentielle à une composante fortement connexe.

D'avance merci de m'éclairer.