BFS, búsqueda en amplitud
Primero recorre las áreas más cercanas al punto inicial, luego las áreas más alejadas, hasta completar el gráfico. Primero recorra todos los puntos con una distancia de 1 desde el punto de partida y luego vaya a todos los puntos con una distancia de 2...
Para una implementación específica, se necesita una cola para el almacenamiento auxiliar.
Por ejemplo, S es el punto inicial y S es adyacente a tres puntos A, B y C. A es adyacente a A1 y A2, B es adyacente a B1 y B2 y C no es adyacente a otros puntos. Lo que sucede al atravesar A es que A1 y A2 se "descubren". Sin embargo, A1 y A2 no se pueden atravesar inmediatamente, lo que va en contra del propósito de que BFS y C deban atravesarse primero. Y dado que B y C definitivamente se "descubren" antes que A1 y A2, esto refleja una naturaleza de "primero en entrar, primero en salir", por lo que se necesita una cola para almacenar temporalmente los nodos expandidos
BFS()
{
cola q;
q.push(s);//El punto s inicial
mientras (q no está vacío)
{
Obtener un elemento de q
"Descubrir" el elemento sin ingresar al nodo de q Enqueue
}
}
DFS, búsqueda en profundidad
Primero seleccione una ruta y recorra los puntos en la ruta. Luego, comenzando desde el final del camino, da un paso atrás, atravesando otros caminos y los puntos encima de ellos en cada rama.
La implementación específica a menudo se escribe como recursión, por lo que puede entenderse como almacenamiento auxiliar a través de la pila.
Aún con la distancia anterior, una de las secuencias producidas por DFS es S,A,A1,A2,B,B1,B2,C. Las rutas S, A y A1 son las primeras rutas seleccionadas, luego retroceda y seleccione gradualmente otras ramas, A2 se selecciona como la segunda ruta en A, y así sucesivamente. Dado que las operaciones realizadas en cada punto son "descubrimiento", "recorrido" y "rebobinado", los tipos de operaciones son los mismos, por lo que a menudo se escriben como recursivas. . .
DFS(int target)
{
for(cada punto de descubrimiento del objetivo)
{
DFS (el punto de descubrimiento)
}
//Finalizar la función es en realidad el proceso de revertir
}