Représentation des graphes

Représentation des graphes:

Les graphes peuvent être représentés  par :

- matrice : représentation statique

-Liste : représentation dynamique

1.Représentation statique : par matrice

Le graphe est stocké dans une matrice ( tableau à deux dimensions )de valeurs booléennes ou binaires. Chaque case (x, y) du tableau est égale à vrai (1) s’il existe un arc de x vers y, et faux (0) sinon. 

Var 

       G : Tableau[n,n] de booléen ;

Exemple :

             

 est représenté par : 
     



Pour un graphe étiqueté les valeurs de la matrice prennent les valeurs des étiquettes , avec une valeur particulière pour les arcs inexistant. 

 
est représenté par:  


Les arcs inexistants sont représenté par la valeur : -2

2.Représentation dynamique : par liste

Les successeurs d’un nœud sont rangés dans une liste linéaire chainée. Le graphe est représenté par un tableau T où T [i] contient la tête de la liste des successeurs du sommet numéro i. 

Type 

sommet=^cellule;

cellule = Structure

Suc : entier ;

Suivant  :  sommet ;

Fin ;

Var 

 Graphe : Tableau[n] de sommet;

( n nombre des sommets)

  

  est représenté par