Herramientas de usuario
algoritmos-oia:grafos:bfs
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos:bfs [2018/01/05 22:47] santo |
algoritmos-oia:grafos:bfs [2018/01/05 22:58] (actual) santo [Cálculo de distancias] |
||
|---|---|---|---|
| Línea 123: | Línea 123: | ||
| Los nodos que quedan sin encontrar nunca entonces son los no alcanzables, y por lo tanto su distancia es infinito. Con lo cual, es adecuado nuestro valor de inicialización: ponemos todo en infinito, y para aquellos que sean encontrados, la distancia será reemplazada por la distancia verdadera, y quedarán en infinito exactamente los que BFS no recorra, que son aquellos de verdad imposibles de alcanzar. | Los nodos que quedan sin encontrar nunca entonces son los no alcanzables, y por lo tanto su distancia es infinito. Con lo cual, es adecuado nuestro valor de inicialización: ponemos todo en infinito, y para aquellos que sean encontrados, la distancia será reemplazada por la distancia verdadera, y quedarán en infinito exactamente los que BFS no recorra, que son aquellos de verdad imposibles de alcanzar. | ||
| + | Si quisiéramos recorrer **todo** el grafo (por ejemplo, para contar componentes conexas de un grafo no dirigido), lo que podemos hacer generalmente es un for que itere todos los nodos, y cada vez que encuentre un nodo que aún no fue nunca visitado, lance una exploración de BFS nueva con origen en ese nodo, la cual recorrerá todos los alcanzables desde él. | ||
| ===== Cálculo de caminos mínimos ===== | ===== Cálculo de caminos mínimos ===== | ||
| Línea 129: | Línea 130: | ||
| Ya hemos visto de hecho cómo calcular las distancias, es decir, las **longitudes** de esos caminos mínimos. Pero nos faltaría saber cómo calcular los caminos mínimos en sí. | Ya hemos visto de hecho cómo calcular las distancias, es decir, las **longitudes** de esos caminos mínimos. Pero nos faltaría saber cómo calcular los caminos mínimos en sí. | ||
| - | La forma ideal de representar los caminos en BFS es mediante un [[algoritmos-oia:grafos:arboles|árbol]] particular: concretamente, un árbol [[algoritmos-oia:grafos:definiciones|con raíz]] en el nodo origen. El árbol así formado es un [[algoritmos-oia:grafos:dag-caminos-minimos|árbol de caminos mínimos]]: un camino mínimo de un nodo cualquiera hasta el origen, se obtendrá siguiendo el camino en el árbol desde el nodo hasta la raíz. | + | La forma ideal de representar los caminos en BFS es mediante un [[algoritmos-oia:grafos:arboles|árbol]] particular: concretamente, un árbol [[algoritmos-oia:grafos:definiciones|con raíz]] en el nodo origen. El árbol así formado es un [[algoritmos-oia:grafos:dag-caminos-minimos|árbol de caminos mínimos]]: un camino mínimo desde el origen hasta un nodo cualquiera, se obtendrá (en orden inverso) siguiendo el camino en el árbol desde el nodo objetivo hasta la raíz. |
| - | La forma de generar este árbol es manteniendo para cada nodo, su **padre** en el árbol de caminos mínimos. Este nodo padre será el nodo rosa **a través del cuál fue descubierto**. Pensemos en términos de las "capas" de distancia de la onda expansiva: un nodo a distancia 2, se descubre (se vuelve un nodo rosa) gracias a que es encontrado al explorar los vecinos de un nodo a distancia 1 (pues una capa descubre la siguiente). Si vamos recorriendo un camino hacia atrás, **que siempre baje en uno** la distancia al origen, sin dudas el camino en cuestión será mínimo. Eso es lo que se hace al guardar el "padre" de cada nodo: se guarda a qué nodo se debe ir a continuación, para acercarse en al origen. | + | La forma de generar este árbol es manteniendo para cada nodo, su **padre** en el árbol de caminos mínimos. Este nodo padre será el nodo rosa **a través del cuál fue descubierto**. Pensemos en términos de las "capas" de distancia de la onda expansiva: un nodo a distancia 2, se descubre (se vuelve un nodo rosa) gracias a que es encontrado al explorar los vecinos de un nodo a distancia 1 (pues una capa descubre la siguiente). Si vamos recorriendo un camino hacia atrás, **que siempre baje en uno** la distancia al origen, sin dudas el camino en cuestión será mínimo. Eso es lo que se hace al guardar el "padre" de cada nodo: se guarda a qué nodo se debe ir a continuación, para acercarse estrictamente al origen. |
| De esta manera, una vez completada la ejecución y teniendo todos los padres, para formar el camino desde el origen hasta un cierto nodo, se comienza por el final: a partir del nodo destino, vamos viendo "de dónde se vino", siguiendo los "padres" en el árbol hasta dar con el comienzo. De esta forma se reconstruye un camino óptimo "marcha atrás". | De esta manera, una vez completada la ejecución y teniendo todos los padres, para formar el camino desde el origen hasta un cierto nodo, se comienza por el final: a partir del nodo destino, vamos viendo "de dónde se vino", siguiendo los "padres" en el árbol hasta dar con el comienzo. De esta forma se reconstruye un camino óptimo "marcha atrás". | ||
| Línea 172: | Línea 173: | ||
| Suponiendo que explorar los vecinos de un nodo tiene un costo proporcional a su grado (por ejemplo, como ocurre al usar listas de adyacencia), todas estas versiones del algoritmo tienen una complejidad $O(n+m)$. | Suponiendo que explorar los vecinos de un nodo tiene un costo proporcional a su grado (por ejemplo, como ocurre al usar listas de adyacencia), todas estas versiones del algoritmo tienen una complejidad $O(n+m)$. | ||
| - | Esto es porque cada nodo es procesado cuando es rosa, y un nodo es rosa durante **únicamente un paso**. Por lo tanto, se trabaja con un nodo explorando sus vecinos **una única vez** en todo el algoritmo. Si explorar los vecinos de un nodo cuesta proporcional a su grado, el costo total del algoritmo, además de un $O(N)$ fijo para crear el arreglo de visitados y similares estructuras, tendrá un costo igual a la suma de todos los grados, que es $2m$. Por lo tanto el total es $O(n+m)$, proporcional al total de nodos y ejes del grafo, lo cual es muy bueno. | + | Esto es porque cada nodo es procesado cuando es rosa, y un nodo es rosa durante **únicamente un paso**. Por lo tanto, se trabaja con un nodo explorando sus vecinos **una única vez** en todo el algoritmo. Si explorar los vecinos de un nodo cuesta proporcional a su grado, el costo total del algoritmo, además de un $O(n)$ fijo para crear el arreglo de visitados y similares estructuras, tendrá un costo igual a la suma de todos los grados, que es $2m$. Por lo tanto el total es $O(n+m)$, proporcional al total de nodos y ejes del grafo, lo cual es muy bueno. |
| Si se utilizara matriz de adyacencia, el costo de buscar los vecinos de un nodo sería siempre $O(n)$, sin importar su grado. En este caso, el costo de explorar cada uno de los $n$ nodos sería siempre $n$, y en total el costo sería $O(n^2)$. Muchas veces es perfectamente razonable un costo de $O(n^2)$, y en estos casos se puede utilizar perfectamente BFS con matriz de adyacencia. | Si se utilizara matriz de adyacencia, el costo de buscar los vecinos de un nodo sería siempre $O(n)$, sin importar su grado. En este caso, el costo de explorar cada uno de los $n$ nodos sería siempre $n$, y en total el costo sería $O(n^2)$. Muchas veces es perfectamente razonable un costo de $O(n^2)$, y en estos casos se puede utilizar perfectamente BFS con matriz de adyacencia. | ||
algoritmos-oia/grafos/bfs.1515192450.txt.gz · Última modificación: 2018/01/05 22:47 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
