Parcours Graphe

Question 1

Quelle structure de données utilise BFS ?

Answer 1

Une file (queue) FIFO

Question 2

Quelle est la complexité de BFS avec une liste d’adjacence ?

Answer 2

Θ(n + a), où n = sommets, a = arêtes

Question 3

Quel parcours est utilisé pour l’ordre topologique ?

Answer 3

DFS (profondeur)

Question 4

À quoi servent les couleurs blanc, gris et noir dans DFS ?

Answer 4

Blanc = non découvert, Gris = découvert, Noir = visité

Question 5

Quelles composantes DFS permet-il de détecter ?

Answer 5

Cycles, composantes fortement connexes, ordre topologique

Question 6

Quelle structure utilise BFS ?

Answer 6

Une file FIFO

Question 7

Quelle structure utilise DFS ?

Answer 7

Une pile (implémentée par récursivité)

Question 8

Vrai ou Faux : BFS peut détecter des cycles dans un graphe orienté

Answer 8

Faux BFS ne détecte pas de cycles dans un graphe orienté, parce qu’elle marque un sommet dès la première visite et n’explore pas ensuite les arêtes « de retour » qui pourraient boucler vers un ancêtre.

Question 9

Vrai ou Faux : DFS ne peut pas servir à détecter les cycles

Answer 9

Faux

Question 10

À quoi servent les couleurs dans DFS ?

Answer 10

Blanc = non découvert, Gris = découvert, Noir = terminé

Question 11

Quelle est la complexité de BFS avec une matrice d’adjacence ?

Answer 11

Θ(n²)

Question 12

Quel est l’ordre d’exploration de DFS ?

Answer 12

Explore en profondeur jusqu’à ce qu’un chemin échoue

Question 13

Quel est l’ordre d’exploration de BFS ?

Answer 13

Explore tous les voisins d’abord (niveau par niveau)

Question 14

Quel parcours est utilisé pour l’ordre topologique ?

Answer 14

DFS sur un graphe orienté acyclique (DAG)

Question 15

Qu’est-ce qu’un DAG ?

Answer 15

Un graphe orienté sans cycle (Directed Acyclic Graph)

Question 16

Vrai ou Faux : Un graphe non-orienté peut avoir un ordre topologique

Answer 16

Faux

Question 17

BFS garantit-il un chemin minimal en nombre d’arêtes ?

Answer 17

Oui

Question 18

Dans DFS, quand enregistre-t-on les timestamps ?

Answer 18

Au début (découverte) et à la fin (fin d’exploration)

Question 19

Quel algorithme est souvent utilisé pour les composantes fortement connexes ?

Answer 19

Kosaraju ou Tarjan (basés sur DFS)

Question 20

Quel parcours permet de construire un arbre de parcours ?

Answer 20

BFS ou DFS selon l’algorithme

Question 21

Vrai ou Faux : Le graphe obtenu par DFS est toujours un arbre

Answer 21

Faux, seulement les arêtes de découverte forment un arbre

Question 22

Quel est l’ordre des timestamps dans un DFS fini ?

Answer 22

Découverte < fin

Question 23

Pseudo-code : que fait-on après avoir visité tous les voisins d’un sommet u en DFS ?

Answer 23

On passe u en noir et on enregistre son temps de fin

Question 24

Vrai ou Faux : Un sommet gris peut avoir un voisin blanc

Answer 24

Vrai

Question 25

Que signifie un cycle dans un graphe orienté détecté par DFS ?

Answer 25

Présence d’une arête arrière (back edge)

Question 26

Que veut dire DFS ?

Answer 26

DFS signifie Depth-First Search. C'est un algorithme de parcours de graphe qui explore les sommets en profondeur avant de revenir en arrière.

Question 27

Explique pourquoi DFS peut détecter des cycles dans un graphe orienté.

Answer 27

Parce qu'on peut rencontrer un sommet déjà découvert (gris) lors de l’exploration, ce qui indique un cycle.

Question 28

Explique pourquoi BFS est utilisé pour trouver le chemin le plus court.

Answer 28

Parce qu’il explore les sommets par niveau (distance croissante), donc la première fois qu’on atteint un sommet, c’est avec le plus court chemin.

Question 29

Pourquoi DFS utilise-t-il une pile ?

Answer 29

Parce qu’il doit revenir en arrière dès qu’un chemin est terminé. La pile permet de mémoriser l'ordre de retour.

Question 30

Que représente un arbre de parcours dans DFS ?

Answer 30

C’est l’ensemble des arêtes de découverte formant une structure arborescente à partir du sommet source.

Question 31

Quell est le parcours BFS (Breadth-First Search) ou parcours en largeur en francais pour cet arbre. A / \ B C / \ D E

Answer 31

L’ordre de BFS depuis A est : A, B, C, D, E

Question 32

Complète le pseudo-code de DFS : DFS(u): u.couleur ← gris pour chaque v dans voisins(u): SI v.couleur == ______ alors DFS(v)

Answer 32

blanc

Question 33

Complète le pseudo-code de BFS : BFS(s): Q ← file vide Q.ajouter_fin(s) TANT QUE Q non vide: u ← Q.sortir_premier() pour chaque v dans voisins(u): SI v non visité alors ______

Answer 33

Q.ajouter_fin(v)

Question 34

Quand BFS ne fonctionne-t-il pas pour trouver le plus court chemin ?

Answer 34

Quand les poids sont différents de 1 (il faut Dijkstra)

Question 35

Quand DFS ne permet-il pas de trouver un chemin optimal ?

Answer 35

Quand il faut minimiser le nombre d’arêtes ou un coût

Question 36

Complexité de BFS sur liste d'adjacence ?

Answer 36

Θ(n + a)

Question 37

Complexité de DFS sur matrice d'adjacence ?

Answer 37

Θ(n²)

Question 38

Vrai ou faux : Une matrice d’adjacence est toujours symétrique pour un graphe non orienté.

Answer 38

Vrai

Question 39

Vrai ou faux : Les listes d’adjacence sont plus efficaces pour les graphes denses.

Answer 39

Faux

Question 40

Vrai ou faux : Les matrices d’adjacence sont plus efficaces pour vérifier l'existence d'une arête.

Answer 40

Vrai

Question 41

Vrai ou faux : BFS est plus rapide avec une liste d’adjacence qu’avec une matrice.

Answer 41

Vrai

Question 42

Quelle est la complexité mémoire d'une matrice d’adjacence ?

Answer 42

Θ(n²)

Question 43

Quelle est la complexité mémoire d'une liste d’adjacence ?

Answer 43

Θ(n + a)

Question 44

Comment détecter si un graphe est orienté à partir d'une matrice d’adjacence ?

Answer 44

La matrice n’est pas symétrique (M[u][v] ≠ M[v][u] pour certains u, v)

Question 45

Quelle est la complexité pour vérifier l’existence d’une arête (u,v) dans une matrice d’adjacence ?

Answer 45

Θ(1)

Question 46

Quelle est la complexité pour vérifier l’existence d’une arête (u,v) dans une liste d’adjacence ?

Answer 46

Θ(degré(u))

Question 47

Quel est le meilleur format pour représenter un graphe clairsemé ?

Answer 47

Liste d’adjacence

Question 48

Comment traduire une matrice d’adjacence en liste d’adjacence ?

Answer 48

Pour chaque ligne u, ajouter v à la liste de u si M[u][v] == 1

Question 49

Complète : La matrice d’un graphe non orienté est __________.

Answer 49

symétrique

Question 50

Complète : La représentation en liste d’adjacence est meilleure pour les graphes __________.

Answer 50

clairsemés

Question 51

Complète : La complexité mémoire de la liste d’adjacence est __________.

Answer 51

Θ(n + a)

Question 52

Complète : Dans une matrice d’adjacence, une valeur de 1 à la position (u,v) signifie __________.

Answer 52

qu’il existe une arête de u vers v

Question 53

Complète : Pour parcourir tous les voisins d’un sommet dans une liste d’adjacence, la complexité est __________.

Answer 53

Θ(degré(u))

Question 54

Qu'est-ce que le parcours en largeur (BFS) ?

Answer 54

Le parcours en largeur (BFS) parcourt les nœuds d’un graphe à partir d’un sommet source. Le parcours se fait niveau par niveau par rapport à la distance au nœud source. ## Footnote Comme l’algorithme de Dijkstra mais avec des poids d’arêtes à 1.

Question 55

Comment fonctionne le parcours en profondeur (DFS) ?

Answer 55

Le parcours en profondeur (DFS) explore les nœuds d’un graphe en allant aussi profondément que possible avant de revenir en arrière. On garde en mémoire deux temps : temps de découverte et temps de fin.

Question 56

Quelle structure est utilisée dans BFS pour gérer les sommets à visiter ?

Answer 56

Dans BFS, on utilise une file (queue) pour gérer les sommets à visiter. Chaque sommet est marqué avec une couleur, et on met à jour la distance du sommet et son prédécesseur.

Question 57

Quelle structure est utilisée dans DFS ?

Answer 57

Dans DFS, la structure utilisée est une pile (implémentée par récursion). On colore les nœuds en blanc, gris, puis noir selon leur état.

Question 58

Quelles sont les limitations de l'algorithme de Dijkstra ?

Answer 58

Dijkstra est un algorithme de plus court chemin qui ne fonctionne pas si le graphe contient des poids négatifs. Il utilise une file de priorité pour toujours explorer le sommet avec la distance minimale.

Question 59

Comment fonctionne l'algorithme de Kruskal ?

Answer 59

Kruskal construit un arbre couvrant de poids minimal (ACM) en triant les arêtes par poids croissant et en utilisant une structure de type Union-Find (ensembles disjoints) pour éviter les cycles.

Question 60

Comment fonctionne l'algorithme de Prim ?

Answer 60

Prim construit l’ACM en partant d’un sommet arbitraire et en ajoutant à chaque étape l’arête de poids minimal qui relie un sommet visité à un sommet non visité.

Question 61

Si on utilise un parcours en largeur, comment va t il parcourir les noeuds?

Answer 61

Le parcours en largeur (en. Breadth-First Search) parcours les noeuds d’un graphe à partir d’un noeud source donné en entrée. Le parcours se fait niveau par niveau par rapport à la distance au noeud source. IE. Parcourt tous les noeuds à distance de 1 ensuite tous les noeuds à distance de 2, etc. Enfaite il fonctionne exactement comme l'algorithme de Djikstra mais ici tous les poids des arcs/arêtes sont de 1.

Question 62

Avec quel type de graphe le parcours en largeur fonctionne t il?

Answer 62

Il fonctionne avec Graphe orienté ou non orienté

Question 63

Lien entre BFS (parcours en largeur) et Djisktra

Answer 63

BFS fonctionne exactement comme Dijkstra dans le cas où tous les poids des arcs/arêtes sont égaux à 1. - Il garantit alors un plus court chemin en nombre d’arêtes. - Il utilise une file FIFO au lieu d’une file de priorité.