Algorithme débutant

u  Un graphe est un ensemble de nœuds reliés par des liens. 

u  Ce n'est plus un arbre dès qu'il existe deux parcours différents pour aller d'au moins un nœud vers un autre.

u  Un graphe est connexe, lorsqu'il est possible de trouver au moins un parcours permettant de relier les nœuds deux à deux (un arbre est un graphe connexe).

u  Un graphe est dit pondéré lorsqu'à chaque lien est associé une valeur (appelée poids).

u  On utilisera les graphes pondérés par exemple pour :    - gérer des itinéraires routiers (quelle est la route la plus          courte pour aller d'un nœud à un autre). 

-    gérer des fluides (nœuds reliés par des tuyauteries de       diamètre différents).

-    simuler un trafic routier.

-    simuler un circuit électrique.

u  Un graphe est dit orienté lorsque les liens sont unidirectionnels.

u  On peut représenter un graphe de manière dynamique, comme les arbres. 

u  Une autre solution consiste à numéroter les N sommets et d'utiliser une matrice carrée NxN, avec en ligne i et en colonne j un 0 si les nœuds i et j ne sont pas reliés, le poids de la liaison sinon.

u  Un problème important est le parcours d'un graphe : il faut éviter les boucles infinies, c'est-à-dire retourner sur un nœud déjà visité et repartir dans la même direction.

      Pour cela, on utilise des indicateurs de passage (Booléen) 108      ou une méthode à jeton.