Algoritmos básicos: búsqueda en profundidad (DFS) y búsqueda en amplitud (BFS)

La búsqueda en profundidad y la búsqueda en amplitud son algoritmos de búsqueda de gráficos. Son similares pero diferentes y se utilizan en diferentes aplicaciones. Analicémoslos juntos aquí para facilitar la comparación.

1. Búsqueda en profundidad

La búsqueda en profundidad es un tipo de algoritmo gráfico. Es un algoritmo transversal para gráficos y árboles. La abreviatura en inglés es DFS, que es profundidad. Primera búsqueda. La búsqueda en profundidad es un algoritmo clásico en la teoría de grafos. El algoritmo de búsqueda en profundidad se puede utilizar para generar la tabla de clasificación topológica correspondiente del gráfico de destino. La tabla de clasificación topológica se puede utilizar para resolver convenientemente muchos problemas relacionados con la teoría de grafos. como el problema de ruta máxima y así sucesivamente. Las estructuras de datos del montón se utilizan generalmente para ayudar en la implementación del algoritmo DFS. En pocas palabras, el proceso consiste en profundizar en cada ruta de rama posible hasta que no pueda profundizar más y cada nodo solo pueda visitarse una vez.

Pasos básicos

(1) Para el siguiente árbol, el método DFS comienza primero desde el nodo raíz 1 y el orden de los nodos de búsqueda es 1,2,3,4,5 ,6,7,8 (suponiendo que se prefiere la rama izquierda entre la rama izquierda y la rama derecha).

(2) Acceda al punto en la parte superior de la pila desde la pila

(3) Encuentre los puntos adyacentes a este punto que aún no han sido atravesados, márquelos, y luego colóquelos en la pila, proceda en secuencia

(4) Si este punto no tiene puntos adyacentes que aún no hayan sido atravesados, saque este punto de la pila y luego proceda en secuencia de acuerdo con (3);

(5) hasta que se recorra todo el árbol, todos los elementos de la pila aparecerán y, finalmente, la pila estará vacía y se completará el recorrido DFS.

2. Búsqueda en amplitud

La búsqueda en amplitud (también llamada búsqueda en amplitud, abreviada BFS, que se describe en términos de amplitud a continuación) es un algoritmo transversal para gráficos conectados. Este algoritmo también es prototipo de muchos algoritmos gráficos importantes. Tanto el algoritmo de ruta más corta de fuente única de Dijkstra como el algoritmo de árbol de expansión mínima de Prim adoptan ideas similares a la búsqueda en amplitud. Su alias también se llama BFS, que es un método de búsqueda ciega cuyo propósito es expandir y verificar sistemáticamente todos los nodos en el gráfico para encontrar resultados. En otras palabras, no considera las posibles ubicaciones de los resultados y busca minuciosamente en todo el gráfico hasta encontrar los resultados. El proceso básico, BFS, consiste en comenzar desde el nodo raíz y atravesar los nodos del árbol (gráfico) a lo largo del ancho del árbol (gráfico). Si se visitan todos los nodos, el algoritmo aborta. Las estructuras de datos de cola se utilizan generalmente para ayudar en la implementación del algoritmo BFS.

Pasos básicos

(1) Dado un gráfico conectado, como se muestra en la figura, la inicialización es toda blanca (no visitada)

(2) Punto de inicio de búsqueda V1 (gris);

(3) Se ha buscado V1 (negro), y pronto se buscará V2, V3, V4 (marcado en gris)

(4; ) V2, V3, V4 Repita la operación anterior;

(5) Hasta que el punto final V7 se tiñe de gris, termine;

(6) El camino más corto es V1, V4, V7.