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 | |||
|
algoritmos-oia:grafos:bfs [2018/01/05 22:52] 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 ===== | ||
algoritmos-oia/grafos/bfs.1515192754.txt.gz · Última modificación: 2018/01/05 22:52 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
