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:51] 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 131: | Línea 132: | ||
| 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 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". | ||
algoritmos-oia/grafos/bfs.1515192673.txt.gz · Última modificación: 2018/01/05 22:51 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
