Algorithmique des graphes - Cours 4 – Parcours en profondeur
en tête de la pile est le sommet actuel précédé par la suite de ses ancêtres. Page 10. Parcours en profondeur – graphes non-orientés. A : B
Quelques rappels sur la théorie des graphes
On appelle ordre d'un graphe le nombre de ses sommets i.e c'est card(S). le parcours en profondeur consiste
Parcours dun graphe
1 avr. 2013 Les sommets de ce graphe sont a b
Première partie : Algorithmique avancée pour les graphes
Une façon naïve de déterminer les différentes SCC d'un graphe consiste à faire un parcours (en largeur ou en profondeur) à partir de chacun des sommets du
Théorie des graphes et optimisation dans les graphes Table des
8.4 Parcours en profondeur (Depth First Search = DFS) . donné un tel graphe on pourra s'intéresser
Algorithmique Cours 7 : Parcours de graphes ROB3 – année 2014
) : tous les autres arcs. Arcs associée à un parcours en profondeur. A. B. C. D arc
Graphes : introduction Graphes Graphes Graphes : G = (S A)
parcours en largeur parcours en profondeur
ALGO1 – Parcours en profondeur
7 févr. 2021 1 Parcours en profondeur générique dans un arbre ... C. D. E. F. Théor`eme 2 Soit G = (S A) un graphe. Un parcours en profondeur sur G ...
Algorithmique des graphes - Cours 5 – Composantes fortement
On l'appelle le graphe des composantes fortement connexes. CFC(G). Page 15. Tester la connexité forte avec Parcours en profondeur. Calculer la composante
Parcours de graphes
L'algorithme de parcours en profondeur (DFS) d'un graphe G prend un temps O(n+m) Parcours. Propriétés du parcours en profondeur: A. B. C.
[PDF] Parcours de graphes - IGM
Le parcours d'un graphe en profondeur se réalise en partant d'un sommet arbitraire v à visiter et en parcourant d'abord un de ses voisins u et tous ses “
[PDF] Algorithmique des graphes - Cours 4 – Parcours en profondeur
Algorithme 1 : Parcours en profondeur DFS(G) Données : graphe G marque des sommets (initialisé à Faux) père ? des sommets (initialisée à null)
[PDF] Parcours dun graphe Parcours profondeur dabord
Parcours d'un graphe • un processus dans lequel on visite tous les noeuds que l'on puisse atteindre à partir du noeud initial
[PDF] Parcours dun graphe
Parcours en profondeur Jean-Manuel Mény – IREM de LYON () Algorithmique ISN 2013 47 / 97 Page 66 Parcours en profondeur : principe de l'algorithme Vous
[PDF] Première partie : Algorithmique avancée pour les graphes - CNRS
Une façon naïve de déterminer les différentes SCC d'un graphe consiste à faire un parcours (en largeur ou en profondeur) à partir de chacun des sommets du
[PDF] Quelques rappels sur la théorie des graphes - CNRS
On appelle ordre d'un graphe le nombre de ses sommets i e c'est card(S) le parcours en profondeur consiste à partir d'un sommet donné à suivre un
[PDF] Parcours de graphes - Université de Montréal
L'algorithme de parcours en profondeur (DFS) d'un graphe G prend un temps O(n+m) C D E A Sommets non visités Sommets visités Arêtes non visitées
[PDF] Parcours de graphes
L'algorithme de parcours en profondeur (DFS) d'un graphe G prend un temps O(n+m) Parcours Propriétés du parcours en profondeur: A B C
[PDF] Algorithmique Cours 7 : Parcours de graphes ROB3
) : tous les autres arcs Arcs associée à un parcours en profondeur A B C D arc
[PDF] Parcours de graphes
sommets du graphe Il y a deux stratégies de parcours différentes : partant d'un sommet le graphe est parcouru ? en largeur ? en profondeur
Parcours de graphes
IFT2015, A2009, Sylvie Hamel
Université de Montréal
1Parcours
Un sous-graphe S d'un graphe G est un graphe tel que: Les sommets de S forment un sous-ensemble des sommets de GQuelques définitions
Les arêtes de S forment un sous-ensemble des arêtes de GUn sous-graphe est dit couvrant (spanning) s'il contient tous les sommets de
G2Un graphe G est dit connexe s'il existe un
chemin reliant chaque pair de sommets de GUne composante connexe d'un graphe G
est un sous-graphe connexe maximal de GParcours
Quelques définitions (suite)
© Goodrich et Tamassia 2004© Goodrich et Tamassia 2004IFT2015, A2009, Sylvie Hamel
Université de Montréal
3Parcours
Un arbre A (non raciné) est un graphe non
orienté tel queUne forêt est un graphe non orienté ne
contenant pas de cyclesQuelques définitions (suite)
A est connexeA ne contient pas de cycles
© Goodrich et Tamassia 2004© Goodrich et Tamassia 2004Les composantes connexes d'une forêt sont
donc des arbresIFT2015, A2009, Sylvie Hamel
Université de Montréal
4Parcours
Un arbre couvrant pour un graphe connexe
G est un sous-graphe couvrant qui est un
arbreUne forêt couvrante pour un graphe G est
un sous-graphe couvrant qui est une forêtQuelques définitions (suite)
Un arbre couvrant pour un graphe G n'est
pas unique sauf si G est une arbre© Goodrich et Tamassia 2004
IFT2015, A2009, Sylvie Hamel
Université de Montréal
5Parcours
Parcours en profondeur (Depth-First Search)
Un parcours en profondeur (DFS) d'un graphe G
Visite tous les sommets et toutes les arêtes de GDétermine si G est connexe ou nonCalcule les composantes connexes de GCalcule une forêt couvrante pour G
L'algorithme de parcours en profondeur (DFS) d'un graphe G prend un temps O(n+m) L'algorithme de parcours en profondeur peut être étendu pour résoudre d'autres problèmes sur les graphes: Trouver un chemin entre 2 sommetsTrouver un cycle dans un grapheIFT2015, A2009, Sylvie Hamel
Université de Montréal
6Parcours
Exemple:
© adapté de Goodrich et Tamassia 2004
ABCDE ASommets non explorésSommets visitésArêtes non exploréesArêtes sélectionnéesArêtes de retour
BDCEAIFT2015, A2009, Sylvie Hamel
Université de Montréal
7Parcours
Propriétés du parcours en profondeur:
ABCDEABDCE
Propriété 1: DFS(G,s) visite tous les
sommets et les arêtes de la composante connexe de s Propriété 2: Les arêtes sélectionnées lors du parcours DFS(G,s) forme un arbre couvrant pour la composant connexe de sIFT2015, A2009, Sylvie Hamel
Université de Montréal
8Parcours
Complexité en temps du parcours en profondeur:
Étiquetter ou "lire" l'étiquette d'un sommet ou d'une arête une fois "non exploré" O(1)Chaque sommet est étiquetté deux fois
une fois "visité"une fois "non explorée"Chaque arête est étiquettée deux fois
une fois "sélectionnée" ou "de retour" O(n) O(m) L'opération Incidents(u) est appelée une fois pour chaque sommet u Si notre graphe est représenté par une liste d'adjacences, la complexité en temps de l'algorithme DFS estO(m+n)
IFT2015, A2009, Sylvie Hamel
Université de Montréal
9Parcours
Algorithme de recherche de chemins
Algorithme cheminDFS(G, v, z)
setÉtiquette(v, VISITÉ)P.empiler(v)
si v = z retourner P.éléments()Pour tout e ∈ G.incidents(v)
si étiquette(e) = NON EXPLORÉE w ← opposé(v,e) si étiquette(w) = NON EXPLORÉ setÉtiquette(e, SÉLECTIONNÉE)P.empiler(e)
cheminDFS(G, w, z)P.dépiler()
sinon setÉtiquette(e, DE RETOUR)P.dépiler()
On peut étendre l'algorithme DFS
en un algorithme pour trouver un chemin entre 2 sommets donnés u et zL'idée est d'appeler DFS(G,u), sur
u le premier sommetOn utilise une pile P qui garde en
mémoire un chemin entre le sommet de départ et le sommet courantQuand le sommet final z est atteint
on retourne le contenu de la pile qui contient le chemin cherchéIFT2015, A2009, Sylvie Hamel
Université de Montréal
10Parcours
Algorithme de recherche de cycles
On peut étendre l'algorithme DFS
en un algorithme pour trouver un cycle dans un graphe (s'il en existe un)On utilise une pile P qui garde en
mémoire un chemin entre le sommet de départ v et le sommet courantSi on trouve une arête de retour vers
v, on retourne le cycle trouvé qui est contenu dans la pileAlgorithm cycleDFS(G, v, z)
setÉtiquette(v, VISITÉ)P.empiler(v)
Pour tout e ∈ G.incidents(v)
si Étiquette(e) = NON EXPLORÉE w ← opposé(v,e)P.empiler(e)
si Étiquette(w) = NON EXPLORÉ setÉtiquette(e, SÉLECTIONNÉE) cheminDFS(G, w, z)P.dépiler()
sinonT ← nouvelle pile vide
répéter o ← P.dépiler()T.empiler(o)
tant que o = w retourner T.éléments()P.dépiler()
IFT2015, A2009, Sylvie Hamel
Université de Montréal
11Parcours
Parcours en largeur (Breadth-First Search)
Un parcours en largeur (BFS) d'un graphe G
Visite tous les sommets et toutes les arêtes de GDétermine si G est connexe ou nonCalcule les composantes connexes de GCalcule une forêt couvrante pour G
L'algorithme de parcours en largeur (BFS) d'un graphe G prend un temps O(n+m) L'algorithme de parcours en largeur peut être étendu pour résoudre d'autres problèmes sur les graphes: Trouver le plus court chemin entre 2 sommets Trouver un cycle simple dans un grapheIFT2015, A2009, Sylvie Hamel
Université de Montréal
12Parcours
Exemple:
ASommets non explorésSommets visitésArêtes non exploréesArêtes sélectionnéesArêtes de traverse
E A C F DB AE© adapté de Goodrich et Tamassia 2004
L 0 BL 1 L 2 CDFIFT2015, A2009, Sylvie Hamel
Université de Montréal
13Parcours
Propriétés du parcours en largeur:
Propriété 1: BFS(G,s) visite tous les sommets et les arêtes de la composante connexe de s Propriété 2: Les arêtes sélectionnées lors du parcours DFS(G,s) forme un arbre couvrant pour la composant connexe de s E A C F DB AEL 0 BL 1 Lquotesdbs_dbs44.pdfusesText_44[PDF] parcours en largeur graphe
[PDF] parcours en profondeur itératif
[PDF] algorithme parcours en profondeur python
[PDF] parcours en largeur graphe java
[PDF] conflit de puissance définition
[PDF] parcours lecture acces pas cher
[PDF] parcours lecture pdf
[PDF] parcours lecture le petit chaperon rouge
[PDF] parcours lecture acces avis
[PDF] parcours lecture occasion
[PDF] coexistence pacifique cours
[PDF] archives militaire en ligne
[PDF] livret militaire en ligne
[PDF] la coexistence pacifique de 1953 ? 1962 pdf