GraphesImplémentation en Python
En informatique, il y a 2 méthodes d'implémentation des graphes.
- A l'aide de dictionnaire ,
- A l'aide de la matrice d'adjacence .
Dictionnaire d'adjacence
L'implémentation à l'aide de dictionnaire d'adjacence est la proposition d'implémentation des graphe en python de Guido Von Rossum (l'inventeur du langage Python).
On considère toujours le graphe suivant :
Pour le modéliser, on va utiliser un dictionnaire tel que :
- Les clés soient le noms des sommets (de type str)
- Les valeurs soient un tableau (de type lst) contenant le noms des sommets adjacent à la clé.
Exemple de Construction d'un dictionnaire d'ajacence.#####
- Le sommet
Aest relié aux sommetsAetB=> la clé"A"est donc associée au tableau["A", "B"]. - Le sommet
Best relié aux sommetsAetC=> la clé"B"est donc associée au tableau["A", "C"]. - Le sommet
Cest relié au sommetB=> la clé"C"est donc associée au tableau["B"].
Ainsi pour representer le graphe dans un dictionnaire nommé graphe, on obtient le code suivant :
graphe = {
"A":["A","B"],
"B":["A","C"],
"C":[:::"B"]
}
Exercice
Pour chacun des dictionnaires d'adjacence suivants, déterminer le graphe qui lui correspond.
Dictionnaire 1
graphe = {
"A":["B","C","E"],
"B":["A","D","F"],
"C":["A","E","F","G"],
"D":["B"],
"E":["A","C","G"],
"F":["B","E"],
"G":["C","E"],
}
Graphe
Graphe A
Dictionnaire 2
graphe = {
"A":["C","E","F"],
"B":["D","F"],
"C":["A","C","G","E"],
"D":["B"],
"E":["A","G","C"],
"F":["A","B","E"],
"G":["C","E"],
}
Graphe
Graphe B
Dictionnaire 3
`{py}graphe = {
"A": ["B","C"],
"B":["A", "C", "E"],
"C":["A", "B", "D"],
"D":["C"],
"E":["B"],
},
``
Graphe
Graphe C
Dessiner sur le cours le graphe correspondant au dictionnaire d'adjacence suivant.
graphe = { "A": ["B", "C", "E"] , "B": ["D", "F", "G"], "C": ["A", "G", "F"], "D": ["B", "E"], "E": ["A", "D", "G"], "F": ["B", "C"], "G": ["B", "F", "E"] }
Déterminer le dictionnaire d'adjacence du graphe ci-dessous
Matrice d'adjacence
Après avoir vu l'implémentation sous forme de dictionnaire, maintenant nous allons reprendre les matrices d'adjacence et voir l'implémentation d'un graphe en python, à l'aide de ces matrices
En reprennant, le graphe précédent :
La matrice d'adjacence est donc :
Les matrices sont représentées sous forme de tableaux de tableaux. Ainsi pour représenter ce même graphe, à l'aide , on obtient :
graphe = [
[1, 1, 0],
[1, 0, 1],
[0, 1, 0]]
ou de manière plus concise :
graphe = [ [1, 1, 0], [1, 0, 1], [0, 1, 0]]
Exercice
Pour chacun des dictionnaires d'adjacence suivants, déterminer le graphe qui lui correspond.
Dictionnaire 1
graphe = {
"A":["B","C","E"],
"B":["A","D","F"],
"C":["A","E","F","G"],
"D":["B"],
"E":["A","C","G"],
"F":["B","E"],
"G":["C","E"],
}
Graphe
Graphe A
Dictionnaire 2
graphe = {
"A":["C","E","F"],
"B":["D","F"],
"C":["A","C","G","E"],
"D":["B"],
"E":["A","G","C"],
"F":["A","B","E"],
"G":["C","E"],
}
Graphe
Graphe B
Dictionnaire 3
`{py}graphe = [
[0,1,1,0,0],
[1,0,1,0,1],
[1,1,0,1,0],
[0,0,1,0,0],
[0,1,0,0,0],
]
``
Graphe
Graphe C
Dessiner sur le cours le graphe correspondant à la matrice d'adjacence suivante.
`{py} graphe = {
}`
Déterminer la matrice d'adjacence du graphe ci-dessous.