Implementation (Part 2)
Lección 6 de 9 del curso Búsqueda en profundidad - Algoritmos de grafos de Coddy.
Ahora recorremos todo el grafo con una pila.
Desafío
IntermedioAhora construye el recorrido completo.
Escribe una función llamada dfs que reciba n, el arreglo plano edges (no dirigido) y un vértice start, y devuelva el orden en el que DFS visita los vértices, comenzando en start.
Primero construye la lista de adyacencia (ordena los vecinos de cada vértice de forma ascendente). Luego ejecuta un DFS iterativo con una pila. Solo se visitan los vértices alcanzables desde start.
Para visitar los vecinos en orden ascendente, colócalos en la pila del más grande al más pequeño.
Pruébalo tú mismo
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Escribe el código aquí
*returnSize = 0;
return edges;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Búsqueda en profundidad - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity