[PDF] [PDF] Arbre : Parcours - Algo Prog Objet Python

[PDF] Parcours dun graphe

1 avr 2013 · Exemple de codage : utilisation d'un dictionnaire python Python G=dict() Parcours en profondeur : principe de l'algorithme Vous devez 

[PDF] Python : Graphes - imagecomputingnet

parcours (graphe, voisin, visite) point initial visite=set () parcours (G, "E", visite) Algorithme: parcours en profondeur visiter (noeud): Pour tous mes voisins v

[PDF] Algorithmique - p-fbnet

Bonnefoi, http://ishtar msi unilim fr/, « Arbre Graphe en Python » version du 1er septembre 2011, rédigé avec Parcours récursif en profondeur d'abord

[PDF] Arbre : Parcours - Algo Prog Objet Python

23 Profondeur d'abord itérative • On peut éviter d'utiliser un algorithme récursif pour représenter un parcours en profondeur d'abord • Il faut utiliser une pile

[PDF] Chapitre 3 : Exploration dun graphe - Algorithmique de - LIPN

Principe de l'algorithme Implémentation Complexité Application : tester si un graphe est biparti 3 Parcours en profondeur (DFS) Prolongement d'une chaˆıne  

[PDF] TP no 01 - page du TP

utiliser python comme outil pour l'enseignement Un peu de programmation parcours en largeur et de parcours en profondeur Éventuellement Modifiez votre code afin d'avoir une seule implantation de l'algorithme Cette implantation

[PDF] Algorithmes pour les graphes

24 nov 2016 · Donner les algorithmes de parcours en largeur et en profondeur 2 Programmer l'algorithme de Bellman-Ford en utilisant python et igraph

[PDF] Graphes (Graphs) Implémentations et parcours 1 Représentations

4 nov 2017 · Écrire une fonction qui construit deux vecteurs (listes en Python) in et out Donner le principe de l'algorithme récursif du parcours profondeur

[PDF] Première partie : Algorithmique avancée pour les graphes - CNRS

Lors du parcours en profondeur d'un graphe avec l'algorithme 5, si un successeur sj du sommet s0 est déjà gris, cela implique qu'il existe un chemin permettant d' 

[PDF] Des algorithmes dans les graphes - IRIF

Parcours en profondeur Algorithme important A la base des algorithmes de recherche des composantes fortement connexes (par ex algorithme de Tarjan) et 

[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

[PDF] cornière catnic

[PDF] corniere galva pour brique

[PDF] corniere pour linteau brique

[PDF] cornière support briques

Andrea G. B. Tettamanzi, 20121AlgorithmiqueAlgorithmique Programmation ObjetProgrammation ObjetPythonPython

Andrea G. B. Tettamanzi

Université de Nice Sophia Antipolis

Département Informatique

andrea.tettamanzi@unice.fr

Andrea G. B. Tettamanzi, 20122CM - Séance 9

Arbres

et

Graphes

Andrea G. B. Tettamanzi, 20123Plan

•Arbres -Définitions -Parcours -Réalisation •Graphes

Andrea G. B. Tettamanzi, 20124Arbre

•Structure de données récursive •Un arbre est formé par -Un noeud (dit " racine »), contenant •Des données ou une référence à des données •Des références (ou pointeurs) à des (sous-)arbres -Zéro ou plus sous-arbres •Un noeud n'ayant pas des sous-arbres est dit " feuille » •Les autres noeuds sont dits " noeuds internes » •Nous avons déjà rencontré ce type de structure quand on a

étudié les tas

Andrea G. B. Tettamanzi, 20125Arbre

Andrea G. B. Tettamanzi, 20126Arbre

•La racine r de l'arbre est l'unique noeud ne possédant pas de parent •Tout noeud x qui n'est pas la racine a -un unique parent, noté x.parent ou parent(x) (appelé " père » parfois) -0 ou plusieurs fils ; x.fils ou fils(x) désigne l'ensemble des fils de x •Si x et y sont des noeuds tels que x soit sur le chemin de r à y, -x est un ancêtre de y -y est un descendant de x •Les fuilles n'ont pas de fils

Andrea G. B. Tettamanzi, 20127Arbre

1 e s t l a r a c i n e 9 1 0 6 3 1 1 1 2 8 s o n t l e s f e u il l e s 1 1 e s t u n d e s c e n d a n t d e 4 m a i s p a s d e 2 2 e s t u n a n c t r e d e 1 0

Andrea G. B. Tettamanzi, 20128Arbre

•Quand il n'y a pas d'ambiguïté, on regarde les arêtes d'un arbre comme étant orienté de la racine vers les feuilles •La profondeur d'un noeud (depth) est définie récursivement par -prof(v) = 0, si v est la racine -prof(v) = prof(parent(v)) + 1 •La hauteur d'un noeud (height) est la plus grande profondeur d'une feuille du sous-arbre dont il est la racine

Andrea G. B. Tettamanzi, 20129Arbre

1 e s t l a r a c i n e 2 3 4 s o n t l a p r o f o n d e u r 1 5 6 7 8 l a p r o f o n d e u r 2 L a h a u t e u r d e 2 e s t 2 c e ll e d e 9 e s t 0 c e ll e d e 3 e s t 0 c e ll e d e 1 e s t 4 Andrea G. B. Tettamanzi, 201210Arbre : Utilisation •Les arbres sont un peu partout en Informatique •Représenter la structure syntaxique d'espressions (parsing) -Mathématiques ou logiques -De langages de programmations -Du langage naturel •Gérer des bases de données •Indexation de fichiers. •Tri par tas •Ils permettent des recherches rapides et efficaces.

Andrea G. B. Tettamanzi, 201211Arbre : Parcours

•Parcours (tree traversal) : -on traverse l'ensemble des noeuds de l'arbre •Parcours en largeur d'abord (breadth first) •Parcours en profondeur d'abord (depth first) -Préfixé -Infixé -Postfixé Andrea G. B. Tettamanzi, 201212Parcours en largeur d'abord •On visite la racine •Puis on répète le processus suivant jusqu'à avoir visité tous les sommets : -visiter un fils non visité du sommet le moins récemment visité qui a au moins un fils non visité •On visite tous les sommets à la profondeur 1, •puis tous ceux à la profondeur 2, •puis tous ceux à la profondeur 3 •etc... Andrea G. B. Tettamanzi, 201213Parcours en largeur d'abord L a r g eu r d a b o r d o r d r e d e v i s it e 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 Andrea G. B. Tettamanzi, 201214Parcours en largeur d'abord

Liste ParcoursEnLargeur()

F ← File()

F.enfiler(racine())

L ← Liste()

tant que non F.estVide() x ← F.premier() ; F.défiler()

L.ajouter(x)

pour chaque fils y de x

F.enfiler(y)

renvoyer L Andrea G. B. Tettamanzi, 201215Parcours en largeur d'abord avec passes

Liste ParcoursEnLargeurAvecPasses()

F1 ← File() ; F2 ← File()

F1.enfiler(racine())

L ← Liste()

répéter : tant que non F1.estVide() x ← F1.premier() ; F1.défiler()

L.ajouter(x)

pour chaque fils y de x

F2.enfiler(y)

échanger(F1, F2) # Fin d'une passe, début de la suivante tant que non F1.estVide() renvoyer L Andrea G. B. Tettamanzi, 201216Parcours en largeur d'abord avec passes L a r g e u r d a b o r d a v e c p a s s e s O r d r e d e v i s it e P a s s e 1 1 P a s s e 2 2 3 4 P a s s e 3 5 6 7 8 P a s s e 4 9 1 0 1 1 1 2 Andrea G. B. Tettamanzi, 201217Parcours en profondeur d'abord •Défini de façon récursive •visit(noeud x) previsit(x) pour chaque fils y de x visit(y) postvisit(x) •Premier appel : visit(T.racine()) Andrea G. B. Tettamanzi, 201218Parcours en profondeur d'abord •Ordre préfixé ou postfixé dépend des fonctions previsit et postvisit •Si previsit(x) : met x dans liste -alors liste contient l'ordre préfixé •Si c'est postvisit qui le fait -alors liste contiendra l'ordre postfixé Andrea G. B. Tettamanzi, 201219Parcours en profondeur d'abord O r d r e de v i s it e p r fi x O n m a r q u e q u a n d oquotesdbs_dbs16.pdfusesText_22