11.1. Représentation d'un graphe orienté

Les différentes représentations utilisées pour les graphes non-orientés se prêtent bien à la modélisation d'un graphe orienté :

1. Représentation matricielle : on ne fait figurer l'arc qu'une fois en établissant une convention pour les sommets d'origine (lignes) et les sommets extrémités (colonnes). La matrice de connectivité cesse alors d'être symétrique.

2. Représentation par chaîne de connectivité : on n'insère un arc qu'une seule fois, dans la chaîne du sommet d'origine.

Dans un graphe orienté, un chemin à double sens entre deux sommets doit être explicitement indiqué par deux arcs distincts.

Les arcs étant définis par les couples de sommets de la forme

"X Y"

indiquant un arc allant du sommet X vers le sommet Y (l'ordre dans lequel on énumère les arcs n'a pas d'importance).

11.2. Depth-First Search

Table des matières.

Site Hosting: Bronco