- Escreva uma versão não recursiva do algoritmo de busca em profundidade.
Passo 1
O enunciado pede para escrever uma versão não recursiva do algoritmo de Busca em Profundidade (DFS), que faz parte de teoria de grafos. Para isso precisamos simular a pilha de chamadas da versão recursiva usando uma pilha explícita e manter um vetor de vértices já visitados.
Passo 2
Na abordagem recursiva, cada chamada empilha o estado atual no call stack. Na versão iterativa, vamos usar nossa própria pilha (stack) e gerenciar explicitamente quais vizinhos já foram explorados em cada vértice.
Primeiro, inicializamos um vetor com
para todos os vértices, para marcar quem já foi alcançado, e um vetor
para controlar qual é o próximo vizinho a explorar em cada vértice. Também criamos uma pilha vazia.
Primeiro, inicializamos um vetor
Passo 3
Em seguida, iteramos sobre todos os vértices. Sempre que encontramos um vértice
não visitado, empilhamos
e entramos num loop principal que continua enquanto a pilha não estiver vazia.
No loop, olhamos o vértice no topo da pilha (chamado ). Se ele ainda não foi marcado como visitado, fazemos
. Depois verificamos em
qual é o próximo vizinho não explorado de
.
No loop, olhamos o vértice no topo da pilha (chamado
Passo 4
Se existir um vizinho
na posição
, incrementamos
para apontar ao próximo vizinho em uma futura iteração. Se
ainda não foi visitado, empilhamos
, garantindo que voltaremos a explorar
antes de terminar
.
Se já esgotamos todos os vizinhos de (isto é,
ultrapassou o número de adjacentes), então fazemos
na pilha, simulando o retorno da chamada recursiva em
.
Se já esgotamos todos os vizinhos de
Passo 5
A seguir está o pseudocódigo completo do DFS não recursivo.
Resposta
procedure DFS-Iterativo(G):
// G está em lista de adjacência, V[G] conjunto de vértices
for each u in V[G]:
visited[u] ← false
next[u] ← 1
create empty stack S
for each u in V[G]:
if not visited[u]:
push(S, u)
while S is not empty:
v ← top(S)
if not visited[v]:
visited[v] ← true // pré-processamento de v, se necessário
if next[v] ≤ degree(v):
w ← G.adj[v][ next[v] ]
next[v] ← next[v] + 1
if not visited[w]:
push(S, w)
end if
else:
pop(S) // todos os vizinhos de v já foram explorados (pós-processamento)
end if
end while
end if
end for
// G está em lista de adjacência, V[G] conjunto de vértices
for each u in V[G]:
visited[u] ← false
next[u] ← 1
create empty stack S
for each u in V[G]:
if not visited[u]:
push(S, u)
while S is not empty:
v ← top(S)
if not visited[v]:
visited[v] ← true // pré-processamento de v, se necessário
if next[v] ≤ degree(v):
w ← G.adj[v][ next[v] ]
next[v] ← next[v] + 1
if not visited[w]:
push(S, w)
end if
else:
pop(S) // todos os vizinhos de v já foram explorados (pós-processamento)
end if
end while
end if
end for