---
tags: TNSI, graphes
---
# Représentations d'un graphe
Il est possible de représenter un graphe par un schéma comme nous l'avons déjà vu. Mais pour un traitement informatique, cela est peu efficace.
Comment représenter le graphe suivant en Python ?
```mermaid
graph
A --- B
A --- C
A --- D
B --- C
B --- E
```
## Liste des successeurs
:::info
On peut représenter un graphe non pondéré en donnant, pour chaque sommet, la **liste de ses successeurs** (pour un graphe orienté) ou la **liste de ses voisins** (pour un graphe non orienté).
:::
Avec notre exemple :
- A a pour successeurs B, C et D ;
- B a pour successeurs A, C et E ;
- C a pour successeurs A et B ;
- D a pour sucesseurs A ;
- E a pour successeur B.
En Python, il est commode de coder ceci par un dictionnaire dont les clés sont les noms des sommets et les valeurs sont des tableaux (types `list` ou `tuple`) contenant les noms des successeurs.
Notre exemple pourrait ainsi être codé :
```python
graphe = {
"A" : ["B", "C", "D"],
"B" : ["A", "C", "E"],
"C" : ["A", "B"],
"D" : ["A"],
"E" : ["B"]
}
```
## Matrice d'adjacence
:::info
**Rappel.** Une **matrice** est un tableau rectangulaire de nombres.
:::
On représente souvent les matrices en les encadrant par des parenthèses et en séparant les nombres par des espaces.
>Voici un exemple de matrice
>$\left(\begin{matrix}
>0 & 1 & 3\\
>2 & 3 & 6
>\end{matrix}\right)$
>Cette matrice est constituée de 2 lignes et 3 colonnes.
:::info
Supposons que nous ayons un graphe orienté. On note $n$ le nombre de sommets du graphe.
On commence par numéroter les sommets, de $0$ à $n-1$.
On peut représenter un graphe par une **matrice d'adjacence** avec la méthode suivante :
Le nombre situé à la ligne d'indice $i$ et la colonne d'indice $j$ est égal :
- à 1 si il existe une arête allant du sommet d'indice $i$ vers le sommet d'indice $j$
- à 0 sinon.
Cette matrice est carrée, elle possède $n$ lignes et $n$ colonnes.
:::
Dans le cas où le graphe est non orienté, on considère qu'il est orienté chaque fois "dans les deux sens".
>**Exemple.**
>Le graphe
>```mermaid
>graph
> A --- B
> A --- C
> A --- D
> B --- C
> B --- E
>```
>va être représenté par la matrice d'adjacence :
>$\left(\begin{matrix}0&1&1&1&0\\1&0&1&0&1\\1&1&0&0&0\\1&0&0&0&0\\0&1&0&0&0\end{matrix}\right)$
:::info
Pour représenter un graphe pondéré par une matrice d'adjacence, on procède de même, mais en remplaçant les 1 par les poids des arêtes.
:::
>**Exemple.**
>Le graphe
>```mermaid
> graph
> A -- 3 --- B
> A -- 2 --- C
> A -- 5 --- D
> B -- 1 --- C
> B -- 7 --- E
>```
>va être représenté par la matrice d'adjacence :
>$\left(\begin{matrix}0&3&2&5&0\\3&0&1&0&7\\2&1&0&0&0\\5&0&0&0&0\\0&7&0&0&0\end{matrix}\right)$
En Python, une matrice peut être implémentée par une liste de listes. Chaque ligne est une liste et la matrice est une liste de lignes.
>**Exemple.**
>Le dernier graphe peut être codé par :
```python
g = [[0, 3, 2, 5, 0], # ligne d'indice 0
[3, 0, 1, 0, 7], # ligne d'indice 1
[2, 1, 0, 0, 0], # ligne d'indice 2
[5, 0, 0, 0, 0],
[0, 7, 0, 0, 0]
]
```
>On peut lire l'élément situé à la ligne d'indice 1 et à la colonne d'indice 2 avec :
```python
g[1][2]
```