Gráficos que hacen que DFS y BFS procesen nodos en el mismo orden exacto

Para algunos gráficos, los algoritmos de búsqueda DFS y BFS procesan los nodos en el mismo orden exacto, siempre que ambos comiencen en el mismo nodo. Dos ejemplos son gráficos que son caminos y gráficos con forma de estrella (árboles de profundidad con un número arbitrario de hijos). ¿Hay alguna forma de categorizar gráficos que satisfagan esta propiedad? $1$

algorithms graphs graph-traversal saadtaame
fuente

Tenga en cuenta que en ambos casos esto solo funciona si comienza en algún nodo específico. Si elige un nodo central en una ruta larga, por ejemplo, obtendrá diferentes pedidos de DFS y BFS.

templatetypedef

¿Hay alguna otra posibilidad interesante que una estrella o un camino? A primera vista, parecería que si tuvieras un vértice con un hermano y un hijo, inmediatamente obtendrás diferentes recorridos, por lo que o bien ningún vértice tiene hijos (aparte de la raíz) y obtienes una estrella, o ningún vértice tiene un hermano y obtienes un camino. Supongo que una camarilla también funciona, pero tiene tanto la estrella como el camino incrustado.

Luke Mathieson

@LukeMathieson Estoy pensando en una estrella con el niño más a la derecha como la raíz de otra estrella. Supongo que eso también funcionaría. Incluso podemos hacer una declaración general: si satisface la propiedad cuando la búsqueda comienza en el nodo v∈V, entonces también lo hace una estrella cuyo hijo más a la derecha . Aún mejor, si y satisfacen la propiedad y el nodo es el último procesado en y es donde comienza la búsqueda en , luego agregar el borde del puente crea un gráfico que satisface la propiedad. Reemplazar por también funciona, creo.

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$

saadtaame

Buen punto, por lo que hay algún tipo de composición recursiva a la derecha en la que podrías identificar la hoja derecha del primer gráfico con la raíz del segundo.

Luke Mathieson el

@LukeMathieson Parece que puede solucionar el caso en el que un nodo tiene un hermano y un hijo agregando un borde entre ese hijo y el padre de . Aquí está mi propuesta: Dado un gráfico . , si tal que , entonces la propiedad se mantiene para . El siguiente paso es probar o refutar esta proposición.

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$

saadtaame

Respuestas:

Supongamos que nuestro BFS y dfs tienen una regla para comenzar desde un nodo específico y en cada doble sentido visitan primero el nodo con el grado más bajo:

DFS-BFS

comience desde el nodo negro más a la izquierda, luego (BFS y DFS) visite el nodo rojo más a la izquierda, luego visitará el siguiente nodo negro, y así sucesivamente, para hacerlo más general, puede agregar algunas rutas entre triángulos o agregar estrellas después de terminar los triángulos ...

fuente

Eso es correcto bajo su suposición. En realidad planteaste un buen punto; debemos especificar en qué orden se agregan los nodos a la agenda (pila o cola) cuando se enfrentan a una elección.

saadtaame

Teniendo en cuenta que LIFO y FIFO para la programación producen DFS y BFS respectivamente, se podría argumentar que una programación como esta (en la que la programación puede no ser apilada o en cola) no es una búsqueda de profundidad ni de amplitud, aunque En algunos casos, puede describir su tendencia a parecerse a uno u otro.

Niel de Beaudrap

Creo que se puede implementar en términos de una pila o cola. No cambia la forma en que se quitan las cosas (LIFO o FIFO), cambia el orden en que se agregan los niños (en este caso, primero el grado más bajo).

SamM

@NieldeBeaudrap, en realidad, esto es solo una estructura para mostrar que en algún lugar ambas formas son iguales