Você recebe o DFS se alterar a fila para uma pilha em uma implementação de BFS?

Aqui está o pseudocódigo padrão para a primeira pesquisa de largura:

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

Aqui pushe popsão consideradas operações de fila. Mas e se forem operações de pilha? O algoritmo resultante visita os vértices em ordem de profundidade primeiro?

Se você votou no comentário "isso é trivial", peço que explique por que é trivial. Acho o problema bastante complicado.

algorithms graphs rgrig
fonte

Já vi estudantes lutando com isso, então não acho que seja estritamente simples demais. No entanto, o que mais de "Sim" ou "Não" deve conter uma resposta? A granularidade desejada não está clara na questão.

Raphael

"Sim" viria com um argumento convincente; "no" viria com um contra-exemplo. Mas há melhores respostas do que sim / não, uma vez que você entender o que está acontecendo ...

rgrig

@ Joe, Dave: veja a meta-discussão que se seguiu

Gilles 'SO- stop be evil'

É possível escrever pseudo-código para que, simplesmente mudando poppara uma operação de pilha ou fila, tenhamos dfs ou bfs. Também é fácil escrever pseudocódigo para o qual, a princípio, parece que isso é verdade, mas não é. ics.uci.edu//~eppstein/161/960215.html é uma referência relevante.

31412 Joe

Respostas:

Não, isso não é o mesmo que um DFS.

Considere o gráfico

insira a descrição da imagem aqui

Se você pressionar os nós na ordem da direita para a esquerda, o algoritmo fornecerá uma travessia:

$A, B , E, C , D$

enquanto um DFS esperaria que fosse

$A,B,E,D,C$

O problema ocorre porque você o marca como visto no momento do envio, e não no momento da visita. Conforme apontado nos comentários, se você marcar no momento da visita, seus requisitos de espaço poderão subir para vez de . $\Theta(V+E)$ $\mathcal{O}(V)$

Eu concordo, o problema não é trivial.

Aryabhata
fonte

Isso pressupõe que as listas de adjacência tenham alguma ordem específica fixa. Em matemática, pelo menos, as pessoas são vistas como um conjunto, e um gráfico possui várias travessias de ordem de profundidade, dependendo de como você itera as crianças. (Imagine usar hashes para crianças.) Nesse sentido, a ABECD ainda é uma ordem de profundidade. O interlocutor se pergunta se existe um contra-exemplo mesmo nesse cenário. (Na verdade, este é o lugar onde ele começa a ficar complicado.)

rgrig

@rgrig: Bem, este é um dos possíveis percursos, e isso leva a uma sequência que não está no DFS. Não importa como você itera, marcar como visto resultará em erro DFS 'abaixo' se você não visitar primeiro.

D

$D$

E

$E$

D

$D$

Aryabhata

@Arybhata: Ah, desculpe, eu não sei por que eu estava assumindo que você queria que as bordas fossem direcionadas e apontadas para baixo. Eles não são direcionados, então você está certo: este é um contra-exemplo, mesmo para o que eu estava dizendo no comentário. (Isso é estranho:. Eu tive que escrever mal o seu punho, de modo que não são removidos pelo SE)

rgrig