Pourquoi BFS signe les nœuds avec 2 couleurs, et DFS avec 3 couleurs ?

Question

Cette idée m'est soudain venue à l'esprit.

Pourquoi n'utilise-t-on que 2 couleurs dans les graphes BFS traveral ?

et 3 sont nécessaires pour DFS ?

par exemple : wikipedia :

BFS :

procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t  Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u  G.adjacentVertex(t,e)
13             if u is not marked:
14                  **mark u**
15                  enqueue u onto Q
16     return none

DFS :

  procedure DFS(G,v):
2      label v **as explored**
3      for all edges e in G.adjacentEdges(v) do
4          if edge e is unexplored then
5              w  G.adjacentVertex(v,e)
6              if vertex w is unexplored then
7                  label e as a **discovery edge**
8                  recursively call DFS(G,w)
9              else
10                 label e as a **back edge**

Pourquoi 2 couleurs ne suffisent-elles pas pour DFS ? Pourquoi 3 couleurs sont-elles suffisantes pour BFS ?

voici un autre BFS (cette fois-ci en 3 couleurs) :

Answer 1

Le nombre de couleurs est différent dans chacun des deux algorithmes car ils sont utilisés pour représenter des types d'informations fondamentalement différents.

Dans les systèmes BFS et DFS, les nœuds doivent être marqués comme nœuds inexplorés ou explorés. Deux couleurs sont nécessaires au minimum pour représenter cette information.

Dans l'implémentation DFS que vous avez mentionnée ci-dessus, l'implémentation utilise également des couleurs pour classer les arêtes comme "arêtes de découverte" (arêtes qui forment l'arbre de recherche en profondeur produit par l'algorithme) ou "arêtes de retour" (arêtes qui se déplacent d'une partie profonde de l'arbre DFS vers une partie moins profonde de l'arbre DFS). Ces couleurs sont utilisées pour colorer les arêtes, et non les nœuds. Par conséquent, trois couleurs sont nécessaires pour les arêtes : les arêtes inexplorées, les arêtes de "découverte" et les arêtes arrière.

J'espère que cela vous aidera !

Answer 2

Il peut y avoir des applications de BFS pour lesquelles nous aurions également besoin de 3 couleurs pour les nœuds. Un exemple simple consiste à imprimer chacun sommet et arête d'un graphe non orienté une seule fois à l'aide de BFS. Nous ne pouvons pas le faire avec seulement 2 couleurs. Pour comprendre pourquoi, réfléchissons à l'état du sommet situé à l'autre extrémité de l'arête que nous sommes en train d'explorer (pour une itération). Le sommet à l'autre extrémité peut être (a) déjà traité (b) pas encore découvert (c) déjà dans la file d'attente, en attente de traitement. S'il s'agit de (a), nous avons déjà vu l'arête courante auparavant, nous n'avons donc pas besoin de l'imprimer à nouveau. Pour (b) et (c), nous le voyons pour la première fois et nous devons l'imprimer. D'accord, c'est suffisant. Nous décidons donc de n'utiliser qu'un seul drapeau, visited qui serait true pour (a) et false pour (b) et (c), afin que nous puissions décider quand imprimer un bord et quand ne pas le faire. Mais, en conséquence, nous venons d'établir que nous devrions conserver le fichier visited drapeau false pour les sommets qui se trouvent dans la file d'attente, c'est-à-dire le cas (c). Nous ne pourrons donc pas le marquer lorsque nous le pousserons dans la file d'attente. Nous ne pouvons le marquer que lorsque nous avons exploré toutes les arêtes qui lui sont connectées. Par conséquent, lorsque nous sommes confrontés au cas (c) dans une itération, nous ne pouvons pas savoir si le sommet à l'autre extrémité est déjà dans la file d'attente ou non (à moins que nous ne recherchions explicitement la file d'attente). Nous finirons par le remettre dans la file d'attente et nous obtiendrons une mauvaise réponse.

Answer 3

Si nous expliquons cela en termes simples, dans BFS, une fois que nous avons visité un nœud, cela implique que tous ses voisins sont également visités et que nous n'avons pas besoin de visiter ce sommet à nouveau. Mais en DFS, il existe une opération appelée Backtracking qui implique que nous pouvons avoir besoin de visiter à nouveau un nœud déjà visité et que tous ses voisins ne sont pas visités en même temps. Le fait d'avoir une troisième couleur grise reconnaît le fait que "Oui ! il a été visité et vous n'avez pas besoin de l'imprimer mais il y a des voisins à ce nœud qui ne sont toujours pas visités"