Parcours

Question 1

Parcours de graphe

Answer 1

Visite de tous les sommets accessibles depuis un sommet de départ donné

Question 2

Comment parcourir un graphe

Answer 2

Marquage des sommets par des couleurs :
- Blanc = Pas encore visité
- Gris = En cours d’exploitation
- Noir = On a fini d’exploiter

Au début, le sommet de départ est gris et tous les autres sont blancs
A chaque étape, un sommet gris est sélectionné
Si tous ses voisins sont déjà gris ou noirs, alors il est colorié en noir
Sinon, il colorie un (ou plusieurs) de ses voisins blancs en gris
Jusqu’à ce que tous les sommets soient noirs ou blancs

Question 3

Stockage des sommes gris dans un BFS

Answer 3

File (FIFO)

Question 4

Stockage des sommes gris dans un DFS

Answer 4

Pile (LIFO)

Question 5

Structure de données pour représenter l’arborescence

Answer 5

Tableau π tel que π[si ] = null si si est racine, et π[si ] = père de si sinon

Question 6

BFS (Breadth First Search)

Answer 6

1 Fonction BFS(g, s0)
2 	Soit f une file (FIFO) initialisée à vide
3 	pour chaque sommet si de g faire
4		π[si ] ← null
5 		Colorier si en blanc
6 Ajouter s0 dans f et colorier s0 en gris
7 tant que f n’est pas vide faire
8 	Soit sk le sommet le plus ancien dans f
9 	pour chaque si ∈ succ(sk ) tq si est blanc faire
10 		Ajouter si dans f et colorier si en gris
11 		π[si ] ← sk
12 	Enlever sk de f et colorier sk en noir
13 retourne π

Question 7

Complexité du BFS

Answer 7

O(n + p)
(sous réserve d’une implémentation par listes d’adjacence)

Question 8

Que fait on quand on a le choix entre plusieurs sommets ?

Answer 8

On choisit le plus petit dans l’ordre lexicographique

Question 9

Utilisations possibles d’un BFS

Answer 9

Recherche de plus courts chemins (en nombre d’arêtes)

Question 10

Plus court chemin en nombre d’arêtes

Answer 10

 Fonction calculeDistances(g, s0)
2 	pour chaque sommet si de g faire
3 		π[si ] ← null
4 		Colorier si en blanc
5 		d[si ] ← ∞
6 	Ajouter s0 dans f et colorier s0 en gris
7 	d[s0] ← 0
8 	tant que f n’est pas vide faire
9 		Soit sk le sommet le plus ancien dans f
10 		pour chaque si ∈ succ(sk ) tq si est blanc faire
11 			Ajouter si dans f et colorier si en gris
12			 d[si ] ← d[sk ] + 1
13 			π[si ] ← sk
14 		Enlever sk de f et colorier sk en noir
15 retourne d

Question 11

DFS (Depth First Search)

Answer 11

1 Fonction DFS(g, s0)
2    Soit p une pile (LIFO) initialisée à vide
3	pour tout sommet si ∈ S faire
4 		π[si ] ← null
5 		Colorier si en blanc
6    Empiler s0 dans p et colorier s0 en gris
7    tant que p n’est pas vide faire
8 		Soit si le dernier sommet entré dans p
9 		si ∃sj ∈ succ(si ) tel que sj soit blanc alors
10 			Empiler sj dans p et colorier sj en gris
11 			π[sj ] ← si
12        sinon
13 			Dépiler si de p et colorier si en noir
14   retourne π

Question 12

Complexité du DFS

Answer 12

O(n + p)
(sous réserve d’une implémentation par listes d’adjacence)

Question 13

DFS récursif

Answer 13

1 Proc DFSrec(g, s0)
	Entrée : Un graphe g et un sommet s0
	Précond. : s0 est blanc
2 	début
3 		Colorier s0 en gris
4 		pour tout sj ∈ succ(s0) faire
5 			si sj est blanc alors
6 				π[sj ] ← s0
7 				DFSrec(g, sj )
8 		Colorier s0 en noi

Question 14

Utilisations possibles du DFS

Answer 14

Détection de circuits
Numérotation des sommets
Tri topologique d’un DAG
Recherche des composantes fortement connexes

Question 15

Tri topologique d’un DAG

Answer 15

Ordre total <_topo sur S tel que ∀(si , sj ) ∈ A, si <_topo sj
Après l’exécution de DFSnum, pour tout arc (si , sj ) ∈ A : num[sj ] < num[si ]

Question 16

DAG

Answer 16

Graphe orienté sans circuit