# Représentation

Les graphs peuvent être représenté à l'aide de matrice d'adjacence tel que
\\[
    \begin{cases}
        (i, j) = 1 &\text{ si } (i,j) \in U\\\\
        0 &\text{ sinon }
    \end{cases}
\\]

On y trouve facilement les successeurs en ligne et les prédécesseurs en colones. Mais il faut faire
énormément d'opérations pour vérifier un sommet...

Nous adoptons alors les **listes d'adjacences**. Cette structure possède 2 liste. Une est la
tête (head) et possède autant d'espace que de sommets et est remplie avec des pointeurs vers la
deuxième liste, celle-ci contient les successeurs d'un sommet.

![liste d'adjacence](./liste_dadjacence.png)

On peut alors transformer la liste de successeurs en liste de prédécésseurs

1) calculer \\( d^- \\) 
2) placer dans le nouveau head \\( 1 + \sum^j_i d^-_i\\) où j est la position
3) pour chaques arcs \\( (i,j) \\) dans l'ordre de succ,
    1) réduire \\( Head_j \\) de 1
    2) placer i dans \\( Pred_{(Head_j)} \\) 

![list d'adjacence_pred](liste_adjacence_pred.jpg)


**Remarque**: une fois un graph sous cette forme il est souvent plus difficile de le remttre sous
forme de dessin car les nodes n'ont pas de place définies.
