Dos recorridos del gráfico en la estructura de datos, escriba el algoritmo y las ideas, gracias

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 BFS y se debe atravesar 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, y luego retrocede y selecciona 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

}