T – 4 – Implémenter les graphes | Cercles informatiques

Implémenter un Graphe avec une classe

Nous avons étudié les classes en python. Elles peuvent permettre d'implémenter un graphes de façon très commode, plus simple d'utilisation pour le programmeur. Cela est surtout vrai pour l'implémentation avec une matrice d'adjacence, car dans le cas de la liste d'adjacence, le dictionnaire est très efficace. Voici un exemple d'implémentation de la classe graphe que l'on peut imaginer :

Exemple : implémentation des graphes avec une classe

Implémentation d'un graphe, avec matrice d'ajacence, et en utilisant une classe graphe.

class grapheNoNp() :
    def __init__(self ) :
        self.matrice=[]
        self.sommets=[]
        self.nSommets=self.nAretes=0
    def __str__(self ):
        res="sommets :\n"+str(self.sommets)+"\nAretes :"
        for ligne in self.matrice :
            res=res+"\n"+str(ligne)       
        return res
    def addSommet(self ,s ) :
        n=len(self.sommets)
        self.sommets.append(s)
        self.nSommets+=1
        self.matrice.append([0 for i in range(n)])
        for ligne in self.matrice:
            ligne.append(0)
    def addArete(self,sd,sa) :
        i=self.sommets.index(sd)
        j=self.sommets.index(sa)
        self.matrice[i][j] = self.matrice[j][i]=1
        self.nAretes+=1
    def remSommets(self,s) :
        n=self.sommets.index(s)
        self.sommets.remove(s)
        for ligne in self.matrice :
            del ligne[n]
        del self.matrice[n]
        self.nSommets-=1
    def remArete(self,sd,sa) :
        i=self.sommets.index(sd)
        j=self.sommets.index(sa)
        self.matrice[i][j] = self.matrice[j][i] = 0
        self.nAretes-=1

G=grapheNoNp()
G.addSommet("A") 
G.addSommet("B") 
G.addSommet("C")
print("ajout des sommets A B et C  - G a maintenant ",G.nSommets," sommets\n",str(G))
G.addArete("A","B")
G.addArete("A","C")
G.addArete("C","B")
print("ajout des arêtes A-B A-C et C-B  - G a maintenant ",G.nAretes," Aretes\n",str(G))
G.remSommets("B")
print("on retire le sommet B\n",str(G))
G.remArete("A","C")
print("on retire l arête A-C\n",str(G))

Exercice

Dans l'exercice ci-dessous, vous disposez de la classe grapheNoNp définie ci-dessus.

Dans cet exercice, la classe grapheNoNp étudiée au dessus est implémentée avec les méthodes init str addSommet addArete remSommets et remArete.

Ceci est la fin de cette première séquence sur les graphes. Plus tard dans l'année nous reviendrons sur les grapes, pour les utiliser dans la résolution de problèmes.

Il reste un travail que vous devez faire

Produire une implémentation complète d'un graphe orienté et pondéré en utilisant les matrices d'adjacence. Vous produirez une classe graphePO (graphe pondéré et orienté) avec tout les assert nécessaires (programmation défensive). Vous déposerez le travail à l'endroit spécifié par votre professeur.

Pages : 1 2 3 4