Busca em profundidade

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. A busca em grafo consiste em explorar um grafo, de forma que obtenha um processo sistemático de como caminhar por seus vértices e arestas. Às vezes é preciso visitar todos os vértices de um grafo, às vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices. Se o grafo for uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível. Existem dois métodos de percurso em grafos: percurso em profundidade (depth-first search — DFS) e o percurso em largura (breadth first search — BFS). A ideia básica do DFS é buscar "mais a fundo" no grafo quando possível. …exibir mais conteúdo…

#define arcocorrente w.A #define pred x.V void busca_em_profundidade (Graph* g, Vertex* r) { Vertex* v, * w; Arc* a; for (v = g–>vertices; v < g–>vertices+g–>n; v++) { v–>pred = NULL; v–>arcocorrente = v–>arcs; } v = r–>pred = r; while (1) { a = v–>arcocorrente; if (a != NULL) { /* avança */ w = a–>tip; v–>arcocorrente = a–>next; if (w–>pred == NULL) { w–>pred = v; /* empilha w */ v = w; } } else { /* volta */ if (v == r) break; v = v–>pred; /* desempilha */ } } }
Um vértice v é considerado marcado se v–>pred for diferente de NULL. Pequena variante: poderíamos trocar o while por while (r–>arcocorrente != NULL) { Arc* a = v–>arcocorrente; if (a != NULL) { w =