cours 511 - partie 3
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
DéfinitionAlgorithmes complexes Un graphe est une structure de données composée d’un ensemble de Partie 3sommets, et d’un ensemble de relations entre ces sommets. Si la relation n’est pas orientée, la relation est supposée exister dans les deux sens. Le graphe est dit non orienté ou symétrique. Si les relations sont orientées, le graphe est dit orienté. Une relation est appelée arc (ou arête pour les graphes non orientés). Les sommets sont aussi appelés nœuds ou points.Les graphesS1S2 S3Algorithmes complexes : Les 1 Algorithmes complexes : Les 2graphesgraphesGraphes non orientés Graphes connexes Ensemble des sommets : Un graphe non orienté est dit connexe si on peut aller de tous les sommets vers S = {S1, S2, S3, S4, S5} tous les autres sommets. Ensemble des relations symétriques En suivant cette définition, un graphe peut ne pas être connexe mais avoir des composantes connexes. A = {S1S2, S1S3, S2S3, S3S4, S3S5, S4S5}Composantes S1connexesS1Graphe nonS2 S3 S4connexeS2 S3 S4S5S5Algorithmes complexes : Les 3 Algorithmes complexes : Les 4graphes graphes1Graphes orientés Propriétés d’un graphe Une boucle (autoboucle) est une relation (Si, Si). Si les relations sont orientées, le graphe est dit Un multigraphe est un graphe tel qu’il existe plusieurs arcs (allant orienté.dans le même sens) entre certains sommets. S2 est le successeur de S1. Un graphe simple est un graphe sans boucle et sans arc multiple. Un graphe ...
Voir
Publié par
Langue
Français
Algorithmes complexes Partie 3
Les graphes
Graphes non orientés
Algorithmes complexes : Les graphes
Ensemble des sommets : S = {S1, S2, S3, S4, S5} Ensemble des relations symétriques A = {S1S2, S1S3, S2S3, S3S4, S3S5, S4S5}
S1
S2
S3
S4
S5
Algorithmes complexes : Les graphes
1
3
Définition
Un graphe est une structure de données composée d’un ensemble de sommets, et d’un ensemble de relations entre ces sommets. Si la relation n’est pas orientée, la relation est supposée exister dans les deux sens. Le graphe est dit non orienté ou symétrique. Si les relations sont orientées, le graphe est dit orienté. Une relation est appelée arc (ou arête pour les graphes non orientés). Les sommets sont aussi appelés nœuds ou points.
Graphes connexes
S1
S2
S3
Algorithmes complexes : Les graphes
Un graphe non orienté est dit connexe si on peut aller de tous les sommets vers tous les autres sommets. En suivant cette définition, un graphe peut ne pas être connexe mais avoir des composantes connexes.
S1
S2
S3
S4
S5
Algorithmes complexes : Les graphes
2
Composantes connexes
Graphe non connexe
4
1
Graphes orientés
Si les relations sont orientées, le graphe est dit orienté. S2 est le successeur de S1. S3 est le prédécesseur de S4. S1
S2 S3S4
S5
Algorithmes complexes : Les graphes
Propriétés d’un graphe (suite)
5
Unchemin simpleest un chemin où aucun arc n’est utilisé 2 fois. Uncircuit simpleest une chemin simple dont le sommet de départ et le sommet d’arrivée sont les mêmes. Uncircuit eulérienest un circuit simple qui passe une fois et une seule fois par tous les arcs. Uncircuit hamiltonienest un circuit qui passe une fois et une seule fois par tous les sommets.
S1
S2
Départ & arrivée S1 S1
S3 S2
S3
Algorithmes complexes : Les graphes
S3
S1
S2
S3
7
Propriétés d’un graphe
Uneboucle(autoboucle) est une relation (Si, Si). Unmultigrapheest un graphe tel qu’il existe plusieurs arcs (allant dans le même sens) entre certains sommets. Ungraphe simpleest un graphe sans boucle et sans arc multiple. Un graphe est ditpondérési à chaque arc est associé une valeur représentant le coût de transition de cet arc. Uncheminest une suite d’arcs consécutifs. Lalongueur d’un cheminreprésente le nombre d’arcs composant ce chemin.
S1 S1S1 S1 5 1
S2 S2S3 S2S3 1 Algorithmes complexes : Les graphes
Degré d’un graphe
6
D°(S3) = 5 : Degré du sommet S3, nombre d’arcs entrants ou sortants D+(S3)= 3 : Degré d’émission, nombre d’arcs sortants D-(S3)= 2 : Degré de réception, nombre d’arcs entrants
S1
S2 S3S4
S5
Algorithmes complexes : Les graphes
8
2
Spécification abstraite
Sortegraphe Utiliseentier, sommet, arc, booléen, élément, liste
Opérations: Créer_graphe :→graphe Création d’un graphe vide Sommet : graphe⊗entier→Sommet Retourne le nième sommet Arcs : graphe⊗entier→Liste d’arcs Retourne la liste des arcs sortants du nième sommet Marquer_sommet : graphe⊗entier→graphe Permet de marquer un sommet Est_marqué : graphe⊗entier→booléen Teste le marquage d’un sommet
Algorithmes complexes : Les graphes
S1 Mémorisation sous forme de matrice d’adjacence
Un vecteur de taille max n pour les sommets Une matrice de taille n*n pour les arcs
Nom Sommet 0 S1 1 S2 2 S3 … N-1
S2
0 1 2 … N-1 0 vv 1 v 2 v … N-1
Algorithmes complexes : Les graphes
9
S3
11
Spécification abstraite (suite)
Nb_somment : graphe→entier Retourne le nombre de sommet d’un graphe razMarque : graphe→graphe Supprime tous les marquages d’un graphe Ajouter_sommet : graphe⊗élément→graphe Ajout un élément dans un graphe Ajouter_arc : graphe⊗sommet⊗sommet⊗entier→graphe Ajout un arc entre deux sommets
Fin_sorte
Algorithmes complexes : Les graphes
S1 Mémorisation en table de listes d’adjacence
Les sommets sont stockés dans un vecteur. S2 Les arcs sont stockés dans une liste associée aux sommets. Nom SommetLi 1 2 0 S1 0∅ 1 S2 1∅ 2 S3 … N-1
Algorithmes complexes : Les graphes
S3
∅
10
12
3
Allocation dynamique
S1
Les sommets sont stockés dans une liste. S2 Les arcs sont représentés : par le nom du sommet vers lequel il pointe. ou par un pointeur vers ce sommet. S1 S2S3∅
S2 S1∅
S3 S2∅
∅
∅ Algorithmes complexes : Les graphes
Exemple de parcours en profondeur
S0 S1 S2 S3 S5 S6 S4 S7
S0
S6
Algorithmes complexes : Les graphes
S1
S5
S4
S3
S2
S3
S7
∅
13
15
Parcours en profondeur
1.On choisit un premier sommet qu’on empile. 2.Ce sommet est marqué comme visité. 3.A partir de ce sommet, on empile un sommet fils qui n’a pas été visité. 4.Ce sommet est marqué comme visité. 5.A partir de ce nouveau sommet, on empile un sommet fils qui n’a pas été visité. 6.Ce sommet est marqué comme visité. 7.Ainsi de suite… 8.s jusqu’à trouver unSi on arrive dans une impasse, on dépile les sommet sommet ayant un fils non-marqué. 9.Si on trouve un fils, celui-ci est empilé et marqué. 10.Sinon la pile va se vider complètement. Auquel cas on empile un nouveau sommet parmi ceux non marqué. 11.On recommence le processus à partir du point 3. 12.Une fois la pile vide et tous les éléments marqués, le parcours du graphe est terminé.
par exemple l’affichage d’unRemarque : Le traitement effectué lors du parcours ( sommet) s’effectue lorsqu’un sommet est marqué.
Parcours en largeur
Algorithmes complexes : Les graphes
14
Pour le parcours en largeur, on utilise une file de sommets. 1.On choisit un premier sommet qu’on inclut dans la file. 2.A partir de ce sommet, on met dans la file tous ses fils non marqués. 3.On supprime ce sommet de la file et il est marqué comme visité. 4.On sélectionne le prochain sommet de la file. 5.A partir de ce nouveau sommet, on met dans la file tous ses fils. 6.On supprime ce sommet de la file et il est marqué comme visité. 7.Ainsi de suite… 8.La file va se vider complètement. Auquel cas on ajoute un nouveau sommet parmi ceux non marqué. 9.On recommence le processus à partir du point 3. 10.Une fois la pile vide et tous les éléments marqués, le parcours du graphe est terminé.
Remarque : Le traitement effectué lors du parcours (par exemple l’affichage du graphe) s’effectue lorsqu’un sommet est marqué.
Algorithmes complexes : Les graphes
16
4
Exemple de parcours en largeur
S0 S1 S6 S2 S3 S5 S4 S7
S0
S6
Algorithmes complexes : Les graphes
S1
S5
S4
S2
S3
S7
17
5
