1. 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 visited[ ] com false para todos os vértices, para marcar quem já foi alcançado, e um vetor next[ ] para controlar qual é o próximo vizinho a explorar em cada vértice. Também criamos uma pilha vazia.

Passo 3

Em seguida, iteramos sobre todos os vértices. Sempre que encontramos um vértice u não visitado, empilhamos u 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 v). Se ele ainda não foi marcado como visitado, fazemos visited[v] >=ts true. Depois verificamos em next[v] qual é o próximo vizinho não explorado de v.

Passo 4

Se existir um vizinho w na posição next[v], incrementamos next[v] para apontar ao próximo vizinho em uma futura iteração. Se w ainda não foi visitado, empilhamos w, garantindo que voltaremos a explorar w antes de terminar v.
Se já esgotamos todos os vizinhos de v (isto é, next[v] ultrapassou o número de adjacentes), então fazemos pop na pilha, simulando o retorno da chamada recursiva em v.

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

Exercícios relacionados