DFS
Lição 11 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.
A Busca em Profundidade (Depth-First Search) vai fundo antes de se expandir lateralmente. Começando em um vértice, ela segue uma aresta o mais longe possível, então retrocede (backtracks) e tenta a próxima. A versão iterativa usa uma pilha (stack): remove (pop) um vértice, registra-o e insere (push) seus vizinhos não visitados de volta.
Para fazer com que o DFS produza uma ordem de percurso determinística neste desafio, insira os vizinhos em ordem decrescente (reverse-sorted). Dessa forma, o menor vizinho fica no topo da pilha e é processado primeiro, correspondendo à ordem que um DFS recursivo sobre vizinhos ascendentes produziria.
Cuidado com um vértice sendo inserido duas vezes (vizinhos diferentes podem ter o mesmo vértice). Verifique o conjunto de visitados no topo do loop e pule se já tiver sido visitado.
Desafio
FácilEscreva uma função dfs que recebe um array de inteiros 2D adjacency (cada linha é uma aresta [u, v]) e um inteiro start, e retorna a ordem de visita DFS a partir de start como uma lista de inteiros.
Construa o grafo adicionando cada aresta. DFS iterativo usando uma pilha: remova um vértice da pilha, se não tiver sido visitado, registre-o e adicione seus vizinhos na ordem ordenada inversamente para que o menor seja processado primeiro.
Você deve usar a classe Graph (fornecida em graph) - não use recursos integrados da linguagem (mapas, conjuntos) para modelar a adjacência. Dados auxiliares para o algoritmo (conjuntos de visitados, pilhas) podem usar tipos da biblioteca padrão (stdlib).
Experimente você mesmo
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}