¿Cómo puedo retroceder a un valor anterior en la búsqueda en profundidad en C++?
Aquí, estoy implementando la Búsqueda en Profundidad (DFS) en c++. Sin embargo, no encuentro una forma de retroceder al lugar anterior (es decir, 1->2->3 si 3 es el final de la línea, volver a 2).
¿Puedo usar vectores o pilas para rastrear mis movimientos?
int buscador(int linea[3], int numeroLinea) {
int valor = 0;
if (linea[0] == 1) {
if (haEjecutadoLinea[numeroLinea+1] != 1) {
valor = numeroLinea + 1;
} else {
valor = -1; // aquí necesita retroceder y verificar si está al principio
}
} else if (linea[0] == 2) {
if (haEjecutadoLinea[linea[1]] != 1) {
valor = linea[1];
} else {
valor = -1; // aquí también
}
} else {
if (haEjecutadoLinea[linea[1]] != 1) {
valor = linea[1];
} else if (haEjecutadoLinea[linea[2]] != 1) {
valor = linea[2];
} else {
valor = -1; // aquí también
}
}
if (valor <= maximo && valor >= 2) {
return valor;
} else {
return -1; // aquí también
}
}
davy.ai
Sí, puedes utilizar tanto vectores como pilas para rastrear tus movimientos en un algoritmo de búsqueda en profundidad (DFS, por sus siglas en inglés). Ambas estructuras de datos pueden ser utilizadas para llevar un registro de los nodos visitados, así como del orden en que se recorrieron los nodos.
Usar un vector implicaría declarar un vector de enteros o índices para representar el camino recorrido hasta el momento, y agregar o eliminar valores a medida que se recorre el grafo. Posteriormente, puedes utilizar la función back() para acceder al último elemento del vector y retroceder si es necesario.
Usar una pila implicaría crear una pila de enteros o índices para representar el camino recorrido hasta el momento, y agregar o eliminar valores a medida que se recorre el grafo. Luego, puedes utilizar la función top() para acceder al elemento superior de la pila y retroceder si es necesario.
Ambos métodos tienen sus ventajas y desventajas, por lo que finalmente depende de los requisitos específicos de tu algoritmo DFS.