Graphes qui font que DFS et BFS traitent les nœuds dans le même ordre exact

Pour certains graphiques, les algorithmes de recherche DFS et BFS traitent les nœuds dans le même ordre exact à condition qu'ils commencent tous les deux au même nœud. Deux exemples sont des graphiques qui sont des chemins et des graphiques en forme d'étoile (arbres de profondeur avec un nombre arbitraire d'enfants). Existe-t-il un moyen de catégoriser les graphiques qui satisfont cette propriété? $1$

algorithms graphs graph-traversal saadtaame
la source

Notez que dans les deux cas, cela ne fonctionne que si vous commencez à un nœud spécifique. Si vous choisissez un nœud central sur un long chemin, par exemple, vous récupérerez différents ordres de DFS et BFS.

templatetypedef

Y a-t-il d'autres possibilités intéressantes qu'une étoile ou un chemin? À première vue, il semblerait que si vous aviez un sommet avec à la fois un frère et un enfant, vous obtenez immédiatement des parcours différents, donc aucun sommet n'a d'enfants (à l'exception de la racine) et vous obtenez une étoile, ou aucun sommet n'a un frère et vous obtenez un chemin. Je suppose qu'une clique fonctionne également, mais elle a à la fois l'étoile et le chemin intégrés.

Luke Mathieson

G = (V, E)

$G = (V,E)$

= v

$= v$

G_{1}

$G_1$

G_{2}

$G_2$

v_{1}

$v_1$

G_{1}

$G_1$

v_{2}

$v_2$

G_{2}

$G_2$

(v_{1}, v_{2})

$(v_1, v_2)$

v_{1}

$v_1$

v_{2}

$v_2$

Bon point, donc il y a une sorte de composition récursive à droite où vous pouvez identifier la feuille droite du premier graphique avec la racine du second.

Luke Mathieson

v

$v$

v

$v$

G = (V, E)

$G=(V,E)$

\forall x \in V

$\forall x \in V$

\exists y, z, w \in V

$\exists y,z,w \in V$

(y, x), (z, y), (x, w) \in E

$(y,x),(z,y),(x,w) \in E$

(x, z) \in E ⟹

$(x,z) \in E \implies$

G

$G$

Réponses:

Supposons que nos BFS et dfs ont une règle pour démarrer à partir d'un nœud spécifique et dans chaque sens, ils visitent d'abord le nœud avec le degré le plus bas:

DFS-BFS

commencer à partir du nœud noir le plus à gauche, puis (BFS et DFS) sont visiter le nœud rouge le plus à gauche, puis ils visiteront le nœud noir suivant, et ainsi de suite, pour le rendre plus général, vous pouvez ajouter des chemins entre les triangles ou ajouter une étoile après avoir fini les triangles ...

la source

C'est exact selon votre hypothèse. Vous avez en fait soulevé un bon point; nous devons spécifier dans quel ordre les nœuds sont ajoutés à l'agenda (pile ou file d'attente) face à un choix.

saadtaame

En gardant à l'esprit que LIFO et FIFO pour la planification produisent respectivement DFS et BFS, on pourrait soutenir que la planification telle que celle-ci (dans laquelle la planification ne peut pas être de type pile ou file d'attente) n'est ni une recherche approfondie ni étendue en premier - bien que vous pouvez dans certains cas décrire sa tendance à ressembler à l'un ou à l'autre.

Niel de Beaudrap du

Je pense qu'il peut être implémenté en termes de pile ou de file d'attente. Cela ne change pas la façon dont les choses sont retirées (LIFO ou FIFO), cela change l'ordre dans lequel les enfants sont ajoutés (dans ce cas, le degré le plus bas en premier).

SamM

@NieldeBeaudrap en fait c'est juste une structure pour montrer que quelque part les deux manières sont identiques.