Classe Graphe avec liste d'adjacence

In [57]:
class Graphe:
    #crée un graphe avec un certain nombre de sommets, et pas d'arcs. Les sommets sont numérotés de 0 à nbSommets - 1
    def __init__(self, nbSommets):
        self.listeAdjacences = [ [] for i in range(nbSommets) ]
    
    #entrée : depart et arrive, des entiers entre 0 et n-1, où n = nb de sommets
    #ajoute un arc entre depart et arrive. 
    def ajouterArc(self, depart, arrive):
        self.listeAdjacences[depart].append(arrive)
        
    #retourne les successeurs de depart
    def getSuccesseurs(self, depart):
        return self.listeAdjacences[depart]
    
    #retourne le nombre de sommets
    def getNbSommets(self):
        return len(self.listeAdjacences)
In [56]:
G = Graphe(5)
G.ajouterArc(0, 3)
G.ajouterArc(0, 1)
G.ajouterArc(1, 2)
G.getSuccesseurs(0)
Out[56]:
[3, 1]

Classe Graphe avec matrice d'adjacence

In [44]:
#même interface que Graphe
class GrapheMatrice:
    def __init__(self, nbSommets):
        self.matrice = [ [0 for i in range(nbSommets)] for j in range(nbSommets) ]
        
    def ajouterArc(self, depart, arrive):
        self.matrice[depart][arrive] = 1
        
    def getSuccesseurs(self, depart):
        for j in range(len(self.matrice[depart])):
            if self.matrice[depart][j] > 0:
                yield j
    
    def getNbSommets(self):
        return len(self.matrice)

File

In [45]:
G2 = GrapheMatrice(5)
G2.ajouterArc(0, 3)
G2.ajouterArc(0, 1)
G2.ajouterArc(1, 2)
G2.matrice
Out[45]:
[[0, 1, 0, 1, 0],
 [0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]
In [46]:
class File:
    #crée une file vide
    def __init__(self):
        self.tableau = []
    
    def enfiler(self, element):
        self.tableau.append(element)
        
    def defiler(self):
        return self.tableau.pop(0)
    
    def estVide(self):
        return len(self.tableau) == 0
In [51]:
f = File()
f.enfiler(2)
f.enfiler(5)
f.defiler()
Out[51]:
2

Parcours en largeur

In [52]:
import math

#effectue le parcours en largeur dans le graphe G, depuis le sommet s
#retourne le tableau des distances
def parcoursLargeur(G, s):
    d = [math.inf for i in range(G.getNbSommets())]
    d[s] = 0
    
    f = File()
    f.enfiler(s)
    
    while not f.estVide():
        u = f.defiler()
        for v in G.getSuccesseurs(u):
            if d[v] == math.inf:
                d[v] = d[u] + 1
                f.enfiler(v)
    
    return d
In [55]:
parcoursLargeur(G, 0)
Out[55]:
[0, 1, 2, 1, inf]
In [1]:
#Attention : ne surtout pas écrire un programme abscons qui dépend trop de l'implémentation.
import math

def parcoursLargeur(G, s):
    d = [math.inf for i in range(G.getNbSommets())]
    d[s] = 0
    
    f = []
    f.append(s) #celui qui lit ne comprend pas que f a un comportement de file
    
    while not len(f) == 0:
        u = f.pop(0)
        for v in len(G.matrice[u]):
            if(G.matrice[u][v] == 1) #que signifie cette matrice ?
                if d[v] == math.inf:
                    d[v] = d[u] + 1
                    f.append(v)
    
    return d
In [ ]: