Recorrido de Grafos
El recorrido de grafos visita sistemáticamente los vértices y las aristas de un grafo; la búsqueda en anchura explora nivel por nivel, mientras que la búsqueda en profundidad explora tan profundamente como sea posible antes de retroceder, y juntas sustentan la mayoría de los algoritmos de grafos.
Definition
El recorrido de grafos es el proceso de visitar cada vértice (y examinar cada arista) de un grafo en un orden sistemático; la búsqueda en anchura visita los vértices en orden de distancia desde una fuente, y la búsqueda en profundidad sigue cada camino hasta su final antes de retroceder.
Scope
Este tema cubre las dos estrategias fundamentales de búsqueda en grafos, la búsqueda en anchura (BFS) y la búsqueda en profundidad (DFS), sus implementaciones basadas en colas y pilas, y la información estructural que revelan: alcanzabilidad, componentes conectados, caminos más cortos en grafos no ponderados, ordenación topológica, detección de ciclos y componentes fuertemente conectados. Excluye los caminos más cortos ponderados y los problemas de flujo, que se basan en el recorrido pero se tratan por separado.
Core questions
- ¿En qué se diferencian BFS y DFS en el orden en que visitan los vértices, y qué revela cada uno?
- ¿Cómo calcula BFS los caminos más cortos en un grafo no ponderado?
- ¿Cómo permite DFS la ordenación topológica, la detección de ciclos y la descomposición de componentes?
- ¿Por qué ambos recorridos se ejecutan en tiempo lineal en el número de vértices más las aristas?
- ¿Cómo se utilizan los marcadores de visitados y las estructuras de frontera para evitar volver a visitar vértices?
Key concepts
- búsqueda en anchura (BFS)
- búsqueda en profundidad (DFS)
- conjunto de visitados
- fronteras de cola y pila
- componentes conectados
- ordenación topológica
- detección de ciclos
- componentes fuertemente conectados
Key theories
- Búsqueda en anchura y caminos más cortos no ponderados
- BFS visita los vértices en orden no decreciente de distancia desde la fuente utilizando una cola, por lo que calcula el número mínimo de aristas desde la fuente a cada vértice alcanzable en tiempo lineal.
- Búsqueda en profundidad y algoritmos de grafos lineales
- DFS, con sus tiempos de descubrimiento y finalización y clasificación de aristas, produce algoritmos de tiempo lineal para la ordenación topológica, la detección de ciclos y la búsqueda de componentes fuertemente conectados, según lo sistematizado por Tarjan.
Clinical relevance
Los algoritmos de recorrido están en todas partes: BFS encuentra los recuentos de saltos más cortos en redes no ponderadas y subyace a los rastreadores web y la difusión peer-to-peer; DFS impulsa la resolución de dependencias y los sistemas de construcción mediante la ordenación topológica, la detección de interbloqueos, la resolución de laberintos y rompecabezas, y el análisis de componentes en redes sociales y biológicas.
History
La búsqueda en anchura se remonta al trabajo de Moore de 1959 sobre el enrutamiento de laberintos y esfuerzos independientes relacionados. La búsqueda en profundidad fue establecida sobre una base algorítmica rigurosa por Robert Tarjan en 1972, cuyos algoritmos de tiempo lineal para componentes fuertemente conectados y biconectividad demostraron que DFS es una herramienta general poderosa.
Key figures
- Robert Tarjan
- Edward F. Moore
- John Hopcroft
Related topics
Seminal works
- tarjan1972
- cormen2009
Frequently asked questions
- ¿Cuándo debo usar BFS en lugar de DFS?
- Utilice BFS cuando necesite el camino más corto en términos de número de aristas o desee explorar el grafo en orden de distancia desde una fuente. Utilice DFS para problemas sobre la estructura —ordenación topológica, detección de ciclos, componentes conectados o fuertemente conectados— donde la exploración profunda y el retroceso son naturales.
- ¿Por qué BFS y DFS tienen ambos tiempo lineal?
- Cada vértice se marca como visitado y se procesa una vez, y cada arista se examina un número constante de veces, por lo que el trabajo total es proporcional al número de vértices más el número de aristas, escrito O(V + E).