 |
|
|
| |
| TUTORIEL ALGO/METHODES |
|
|
|
| Expliquez-moi...Les graphes |
| Méthode générale de rangement de données, qui s'applique autant à des problèmes purement mathématiques qu'à des questions de la vie de tous les jours.
(28/10/2005) |
  |
Les données ne sont pas gérées
par un programme de manière aléatoire, mais bien au sein d'une
structure, qui permet de les traiter de manière d'autant plus
pertinentes que cette structure est adaptée à l'algorithme utilisé.
Une structure de graphe représente un exemple de ces agencements
de données, avec les tableaux, les listes, piles et files (lire
notre
article du 08/04/2004), et les arbres (lire notre
article du 26/07/2005).
Survol
Au sein d'une structure en graphe, les données sont reliées
sans ordre particulier. Pour reprendre le concept classique
du noeud, où une valeur correspond à un noeud, un graphe correspond
à un agencement où les noeuds sont reliés entre eux de manière
non linéaire. Il se démarque en cela des autres structures abordées
précédemment. Précisons qu'un arbre est une forme particulière
de graphe, connexe, non orienté et acyclique.
Il existe
en effet plusieurs formes de graphes, et notamment deux grandes
catégories : les graphes orientés et les graphes valués. C'est
ici que s'impose le fait que le graphe tient son nom de l'importance
de sa représentation graphique. Un graphe orienté présente les
liaisons internodales avec des flèches, indiquant le sens du
parcours de l'information. Dans le cas d'un graphe valué, le
sens de la liaison entre deux noeuds se découvre via leur valeur
respective, donnant un poids à chacun. Un graphe peut parfaitement
être à la fois orienté et valué.
Un graphe se définit par nombre de mots-clefs, permettant de
préciser ses spécificités. Ainsi, la liaison entre deux noeuds
est un "arc", le nombre d'arcs entre et sortant d'un noeud correspond
à son "degré", une suite de noeuds est appelée une "chaîne",
la "longueur" de cette dernière correspondant au nombre d'arcs
qui la constituent.
Une "matrice d'adjacence" est un tableau comprenant autant de
lignes et de colonnes que le graphe a de noeuds. Chaque case
indique la distance entre deux noeuds, calculées par la valeur
prise par l'arc (si le graphe est valué), ou 0 s'ils ne sont
pas liés. Si le graphe est non valué, la matrice ne contient
que des 0 et des 1.
En pratique
De manière très terre-à-terre, l'aspect général des graphes
autorise la modélisation de nombreux environnements disparates
: interconnexions routières, liaisons au sein d'un circuit électronique,
plan d'une ville...
 |
Forum |
|
|
Réagissez
dans les forums
de JDN Développeurs
|
L'application la plus connue d'un graphe est le calcul du plus
court chemin pour aller d'un point à un autre. Les mathématiciens
ont pour cela développé nombre d'algorithmes, dont le plus connu
est celui de Dijkstra.
Celui-ce travaille avec un graphe orienté
et connexe (chaque paire de noeuds est reliée par une chaîne),
avec arcs valués, en répartissant les données en trois groupes
:
- examiné : l'ensemble des noeuds pour lesquels
on connaît le plus court chemin de la source aux noeuds de cet
ensemble.
- courant : l'ensemble des noeuds voisins d'un noeud
examiné, mais pas encore examinés eux-mêmes.
- inconnu : l'ensemble des autres noeuds.
Wikipedia
propose une implémentation en pseudocode permettant de comprendre
le fonctionnement de cet algorithme.
Dijkstra(noeuds, fils, distance, debut,
fin)
Pour n parcourant noeuds
n.parcouru := infini //
Peut être implémenté avec -1
n.precedent := 0
Fin pour
debut.parcouru := 0
DejaVu := liste vide
PasEncoreVu := noeuds
Tant que PasEncoreVu != liste vide
n1 := minimum(PasEncoreVu)
// Le noeud dans PasEncoreVu avec parcouru le plus petit
DejaVu.ajouter(n1)
PasEncoreVu.enlever(n1)
Pour n2 parcourant fils(n1)
// Les noeuds reliés à n1 par un arc
Si n2.parcouru > n1.parcouru
+ distance(n1, n2) // distance correspond au poids
de l'arc reliant n1 et n2
n2.parcouru
:= n1.parcouru + distance(n1, n2)
n2.precedent
:= n1 // Dis que pour aller à n2, il faut passer
par n1
Fin si
Fin pour
Fin tant que
chemin := liste vide
n := fin
Tant que n != debut
chemin.ajouterAvant(n)
n := n.precedent
Fin tant que
Renvoyer chemin |
|
|
|
|
|
|
|
| Quand achetez-vous le plus en ligne ? |
|
|
|
|
|
|
|
|
| |
|
