Algorithme 1 : Parcours en largeur BFS(G,s) Données : graphe G, sommet de départ s File D (initialisée à vide), marque des sommets (initialisé à Faux) début
| Previous PDF | Next PDF |
[PDF] Algorithmique des graphes - Cours 3 – Parcours en largeur - LaBRI
Algorithme 1 : Parcours en largeur BFS(G,s) Données : graphe G, sommet de départ s File D (initialisée à vide), marque des sommets (initialisé à Faux) début
[PDF] Parcours dun graphe
1 avr 2013 · Parcours en largeur : principe de l'algorithme Vous devez parcourir toutes les pages d'un site web Les pages sont les sommets d'un graphe
[PDF] Chapitre 3 : Exploration dun graphe - Algorithmique de - LIPN
1 Exploration d'un graphe / Parcours 2 Parcours en largeur (BFS) Partition des sommets en couches Principe de l'algorithme Implémentation Complexité
[PDF] Parcours de graphes - Université de Montréal
Un parcours en profondeur (DFS) d'un graphe G Visite tous les sommets et toutes les arêtes de G Détermine si G est connexe ou non Calcule les
[PDF] Première partie : Algorithmique avancée pour les graphes - CNRS
Algorithme 2 : Parcours en largeur d'un graphe 1 Fonction BFS(g, s0) Entrée : Un graphe g et un sommet s0 de g Postcondition : Retourne une arborescence
[PDF] Algorithmes pour les graphes - CNRS
3 Structures de données pour représenter un graphe 4 Parcours de graphes Généralités sur les parcours Parcours en largeur (BFS) Parcours en profondeur
[PDF] Parcours de graphes - IRIF
2 nov 2010 · Correction du parcours en largeur Théor`eme Soient G = (S,A) un graphe non- orienté et s ∈ S un sommet L'algorithme PL(G,s) : 1 découvre
[PDF] Algorithmique — L3 TD 7 : Parcours de Graphes - IRIF
L'arbre de parcours en largeur résultant sera présenté par un schéma dans lequel les sommets de profondeur égale seront mis `a la même hauteur, le sommet
[PDF] Parcours de graphes - IGM
Parcours de graphes Exemple 9 Voici (a) un arbre binaire, et les numérotations des sommets que l'on peut obtenir en le parcourant (b) en profondeur ou (c) en
[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 4
[PDF] parcours en profondeur d'un graphe en c
[PDF] théorie des graphes python
[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
Algorithmique des graphes
Cours 3 - Parcours en largeur
František Kardoš
frantisek.kardos@u-bordeaux.fr Plan IParcours en largeur
IComplexité des algorithmes
Parcours en largeur ou BFS (Breadth First Search)
Un parcours en largeur explore le graphe à partir d"un sommet donné (sommet de départ ou sommet source). L"algorithme permet de calculer les distances de tous lessommets accessibles depuis le sommet source.L"algorithme simule la transmission d"un message à partir d"un
sommet source, en utilisant l"idée suivante : Tout sommet qui reçoit le message, le transférera à tous ses voisins qui ne l"auront pas encore reçu.Parcours en largeur ou BFS (Breadth First Search)
Un parcours en largeur explore le graphe à partir d"un sommet donné (sommet de départ ou sommet source). L"algorithme permet de calculer les distances de tous lessommets accessibles depuis le sommet source.L"algorithme simule la transmission d"un message à partir d"un
sommet source, en utilisant l"idée suivante : Tout sommet qui reçoit le message, le transférera à tous ses voisins qui ne l"auront pas encore reçu.Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Parcours en largeur
Pour modéliser le fait si un sommet a déjà été visité par le parcours (s"il a reçu le message) ou pas, on utilise le marquage. Pour stocker l"ensemble de sommets ayant reçu le message, mais qui ne l"ont pas encore propagé, on utilise une file (FIFO).Parcours en largeur (brut)Algorithme 1 :Parcours en largeur BFS(G;s)Données :grapheG, sommet de départs
Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finParcours en largeur - calcul de distancesAlgorithme 2 :Parcours en largeur BFS(G;s)Données :grapheG, sommet de départs
Fileq(initialisée à vide), marque des sommets (initialisé àFaux),
distancedistdes sommets depuiss(initialisée à infinie) débutmarque[s] Vrai; enfilersà la fin deq; dist[s] 0 ; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; dist[v] dist[u] +1 ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finParcours en largeur - calcul d"un arbre couvrantAlgorithme 3 :Parcours en largeur BFS(G;s)Données :grapheG, sommet de départs
Fileq(vide), marque (faux) et distance (infinie) des sommets, pèredes sommets (initialisée à null) débutmarque[s] Vrai; enfilersà la fin deq; dist[s] 0 ; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; dist[v] dist[u] +1 ; [v] u; enfilervà la fin deq; fin fin défilerude la tête deq; fin finParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dFaux1null ba;d;e;fFaux1null ce;fFaux1null da;a;b;fFaux1null eb;c;fFaux1null fb;c;d;eFaux1null q:Parcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fFaux1null ce;fFaux1null da;a;b;fFaux1null eb;c;fFaux1null fb;c;d;eFaux1null q:aParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fFaux1null ce;fFaux1null da;a;b;fFaux1null eb;c;fFaux1null fb;c;d;eFaux1null q:aParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fVrai1a ce;fFaux1null da;a;b;fFaux1null eb;c;fFaux1null fb;c;d;eFaux1null q:a;bParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fVrai1a ce;fFaux1null da;a;b;fVrai1a eb;c;fFaux1null fb;c;d;eFaux1null q:a;b;dParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fVrai1a ce;fFaux1null da;a;b;fVrai1a eb;c;fFaux1null fb;c;d;eFaux1null q:a;b;dParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fVrai1a ce;fFaux1null da;a;b;fVrai1a eb;c;fFaux1null fb;c;d;eFaux1null q:b;dParcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fVrai1a ce;fFaux1null da;a;b;fVrai1a eb;c;fFaux1null fb;c;d;eFaux1null q:b;dÀ compléter!Parcours en largeur - exemple
uvoisins deumarquedistancepère ab;d;dVrai0null ba;d;e;fVrai1a ce;fVrai3e da;a;b;fVrai1a eb;c;fVrai2b fb;c;d;eVrai2b q:Parcours en largeur - vocabulaire
Découvrir un sommet = sommet reçoit le messageVisiter un sommet = sommet retransmet le messageBLANC - sommet non découvert encore = sommet n"ayant pas
encore reçu le message GRIS - sommet découvert, mais pas visité = sommet ayant reçu le message, mais ne l"ayant pas encore retransmis NOIR - sommet visité = somme ayant reçu et retransmis le messageParcours en largeur - vocabulaire
Découvrir un sommet = sommet reçoit le messageVisiter un sommet = sommet retransmet le messageBLANC - sommet non découvert encore = sommet n"ayant pas
encore reçu le message GRIS - sommet découvert, mais pas visité = sommet ayant reçu le message, mais ne l"ayant pas encore retransmis NOIR - sommet visité = somme ayant reçu et retransmis le messageParcours en largeur
Proposition
Soit G un graphe et s un sommet de G. Pendant l"exécution de PL(G;s), un sommet v est découvert (et puis visité) si et seulement si v est accessible depuis le sommet de départ s. Les sommets sont découverts dans l"ordre croissant par rapport à la distance depuis s. D"ailleurs, la valeur d(v) calculée pendant l"exécution de PL(G;s)est la distance entre s et v.Parcours en largeur
Proposition
Soit G un graphe et s un sommet de G. Soit C la composante connexe de G contenant C. Après une exécution de PL(G;s), considérons l"ensemble d"arêtesE=f(u;pere(u))ju2V(C);u6=sg:
Le graphe H= (V(C);E)est un arbre couvrant de C.
Complexité algorithmique
Étant donné deux algorithmes différents pour résoudre le même problème, pour en choisir le meilleur on cherche des moyens de comparer leur performance. Une des moyens de mesure l"efficacité d"un algorithme (un programme) est lacomplexité. La complexité est définie comme la quantité de ressources (temps et/ou espace de mémoire) nécessaire pour résoudre un problème algorithmique.Complexité algorithmique
Lorsque la complexité d"un algorithme est étudié, pour déterminer le temps de calcul nécessaire, on considère I le nombre d"exécutions des opérations élémentaires (telles que affectations de valeur à une variable, opérations arithmétiques, tests de comparaison, appels à des fonctions, etc.) I au pire cas I en fonction de la taille de l"entrée I de point de vue asymptotiqueExemple : Complexité de parcours en largeurAlgorithme 4 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finInitialisation (ligne 0) : une opération par sommetExemple : Complexité de parcours en largeurAlgorithme 5 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finInitialisation (ligne 0) : une opération par sommetExemple : Complexité de parcours en largeurAlgorithme 6 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLignes 2,3 : complexité constanteExemple : Complexité de parcours en largeurAlgorithme 7 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLigne 4 : test exécuté au maximumnfoisExemple : Complexité de parcours en largeurAlgorithme 8 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLignes 5 et 12 : chaque sommet est visité au plus une foisExemple : Complexité de parcours en largeurAlgorithme 9 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLigne 6 : pour unufixe, il y ad(u)voisins, donc au plusn1Exemple : Complexité de parcours en largeurAlgorithme 10 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLigne 6 : or, ...Exemple : Complexité de parcours en largeurAlgorithme 11 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLigne 6 : chaque arête est considérée au plus deux fois, doncExemple : Complexité de parcours en largeurAlgorithme 12 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLigne 6 : l"affectation est exécutée au maximum 2mfoisExemple : Complexité de parcours en largeurAlgorithme 13 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLigne 7 : test exécuté au maximum 2mfoisExemple : Complexité de parcours en largeurAlgorithme 14 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finLignes 8 et 9 : exécutées au maximumnfoisExemple : Complexité de parcours en largeurAlgorithme 15 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finNombre d"opérations élémentaires : 3+5n+4mau maximumExemple : Complexité de parcours en largeurAlgorithme 16 :Parcours en largeur BFS(G,s)Données :grapheGànsommets etmarêtes, sommet de
départs Fileq(initialisée à vide), marque des sommets (initialisé à Faux) débutmarque[s] Vrai ; enfilersà la fin deq; tant queqnon videfaireu tête(q) ; pour chaquev voisin de ufairesiv non marquéalorsmarque[v] Vrai ; enfilervà la fin deq; fin fin défilerude la tête deq; fin finComplexité de l"algorithme :O(n+m)