Herramientas de usuario
algoritmos-oia:grafos
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa | |||
|
algoritmos-oia:grafos [2018/01/07 04:58] guty [Algún ejemplito de problema] |
algoritmos-oia:grafos [2018/07/05 14:25] (actual) santo [Representación en la computadora] |
||
|---|---|---|---|
| Línea 89: | Línea 89: | ||
| Similarmente, el uso típico de las listas de adyacencia es recorrer los **vecinos** de un cierto nodo. En nuestro ejemplo, los vecinos del nodo $x$ solamente pueden ser $x-2, x-3, x-7, x+2, x+3$ o $x+7$. Basta entonces verificar cuáles de esos números están entre 1 y 100, y tendremos todos los vecinos de $x$, sin necesidad de armarse todas las listas de adyacencia completas de antemano (aunque podríamos). En casos como este hay incluso [[algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero|trucos comunes]] para programar más fácilmente estos "movimientos". | Similarmente, el uso típico de las listas de adyacencia es recorrer los **vecinos** de un cierto nodo. En nuestro ejemplo, los vecinos del nodo $x$ solamente pueden ser $x-2, x-3, x-7, x+2, x+3$ o $x+7$. Basta entonces verificar cuáles de esos números están entre 1 y 100, y tendremos todos los vecinos de $x$, sin necesidad de armarse todas las listas de adyacencia completas de antemano (aunque podríamos). En casos como este hay incluso [[algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero|trucos comunes]] para programar más fácilmente estos "movimientos". | ||
| + | === Aristas como entidad === | ||
| + | |||
| + | En los ejemplos anteriores, no almacenamos "la arista" en ningún lado, sino que tenemos directamente en cada lugar donde hace falta (la matriz, la lista de adyacencia , etc) directamente la información de la arista. En algunos problemas conviene guardar en la matriz o en las listas directamente "el índice" o "el puntero" a la arista en sí, sobre todo si esta tiene información que puede cambiar. En los casos más comunes hacer esta separación no es necesaria, pero como a veces puede ser útil o hasta necesario se explica este concepto [[algoritmos-oia:grafos:aristas-como-entidad|aquí]]. | ||
| ===== Algún ejemplito de problema ===== | ===== Algún ejemplito de problema ===== | ||
algoritmos-oia/grafos.1515301111.txt.gz · Última modificación: 2018/01/07 04:58 por guty
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
