Gráficos que fazem com que DFS e BFS processem nós na mesma ordem exata

Para alguns gráficos, os algoritmos de pesquisa DFS e BFS processam os nós na mesma ordem exata, desde que ambos iniciem no mesmo nó. Dois exemplos são gráficos com caminhos e gráficos em forma de estrela (árvores de profundidade com um número arbitrário de filhos). Existe alguma maneira de categorizar gráficos que satisfazem essa propriedade? $1$

algorithms graphs graph-traversal saadtaame
fonte

Observe que, nos dois casos, isso só funciona se você iniciar em algum nó específico. Se você escolher um nó central em um caminho longo, por exemplo, receberá de volta pedidos diferentes do DFS e do BFS.

templatetypedef

Existem outras possibilidades interessantes além de uma estrela ou um caminho? À primeira vista, parece que se você tivesse um vértice com um irmão e um filho, obteria imediatamente travessias diferentes; portanto, nenhum vértice tem filhos (além da raiz) e você recebe uma estrela ou nenhum vértice tem um irmão. e você pega um caminho. Acho que uma camarilha também funciona, mas tem a estrela e o caminho incorporados.

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$

Bom ponto, então há algum tipo de composição recursiva correta, na qual você pode identificar a folha direita do primeiro gráfico com a raiz do segundo.

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$

Respostas:

Suponha que nosso BFS e dfs tenham uma regra para iniciar a partir de um nó específico e, em cada caminho, eles visitem o nó com o menor grau:

DFS-BFS

comece do nó mais esquerdo da esquerda e, em seguida (BFS e DFS), visite o nó mais esquerdo, depois do próximo nó preto e assim por diante. Para torná-lo mais geral, você pode adicionar alguns caminhos entre triângulos ou adicionar estrela depois de terminar triângulos ...

fonte

Isso está correto sob sua suposição. Você levantou um bom argumento, na verdade; devemos especificar em que ordem os nós são adicionados à agenda (pilha ou fila) quando confrontados com uma opção.

Saadtaame

Tendo em mente que o LIFO e o FIFO para agendamento produzem DFS e BFS, respectivamente, pode-se argumentar que um agendamento como esse (no qual o agendamento pode não ser do tipo pilha ou fila) não é uma pesquisa de profundidade nem de largura - embora em alguns casos, é possível descrever sua tendência a se parecer com uma ou outra.

Niel de Beaudrap 22/08/2012

Eu acho que pode ser implementado em termos de uma pilha ou fila. Ele não altera a maneira como as coisas são retiradas (LIFO ou FIFO), altera a ordem em que os filhos são adicionados (neste caso, o menor grau primeiro).

SamM 22/08/12

@NieldeBeaudrap, na verdade, isso é apenas uma estrutura para mostrar que em algum lugar os dois lados são iguais.