Implementation (Part 2)
Lição 6 de 9 do curso Busca em Profundidade - Algoritmos de Grafos da Coddy.
Agora, percorremos todo o grafo com uma pilha.
Desafio
MédioAgora construa a travessia completa.
Escreva uma função chamada dfs que receba n, o array plano edges (não direcionado) e um vértice start, e retorne a ordem em que o DFS visita os vértices, começando em start.
Primeiro, construa a lista de adjacência (ordene os vizinhos de cada vértice em ordem crescente). Em seguida, execute um DFS iterativo com uma pilha. Apenas os vértices alcançáveis a partir de start são visitados.
Para visitar os vizinhos em ordem crescente, coloque-os na pilha do maior para o menor.
Experimente você mesmo
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Escreva o código aqui
*returnSize = 0;
return edges;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Busca em Profundidade - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity