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 Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos [2018/01/02 11:16] sebach |
algoritmos-oia:grafos [2018/07/05 14:25] (actual) santo [Representación en la computadora] |
||
|---|---|---|---|
| Línea 3: | Línea 3: | ||
| Clase PAP 2017 Melanie https://git.exactas.uba.ar/ltaravilse/pap-alumnos/blob/master/clases/clase03-grafos/grafos.pdf | Clase PAP 2017 Melanie https://git.exactas.uba.ar/ltaravilse/pap-alumnos/blob/master/clases/clase03-grafos/grafos.pdf | ||
| - | Un grafo es un conjunto de objetos, llamados vértices o nodos, unidos mediantes líneas llamadas aristas. Se los usa para representar muchas cosas, por ejemplo en arquitectura, los nodos pueden representar habitaciones o espacios, y las aristas pueden significar que los espacios unidos comparten una pared. | + | Un grafo es un **conjunto de objetos**, llamados vértices o nodos, **unidos mediantes líneas** llamadas aristas. Se los usa para representar muchas cosas, por ejemplo en arquitectura, los nodos pueden representar habitaciones o espacios, y las aristas pueden significar que los espacios unidos comparten una pared. |
| También se los usa para analizar redes, donde los nodos son computadores y una arista representa que las computadoras que une están conectadas. | También se los usa para analizar redes, donde los nodos son computadores y una arista representa que las computadoras que une están conectadas. | ||
| Línea 36: | Línea 36: | ||
| - | ===== Representación en la compu ===== | + | ===== Representación en la computadora ===== |
| Algo muy importante es cómo guardar un grafo en la computadora. En una hoja es fácil, lo dibujamos y listo. Pero y en la compu? | Algo muy importante es cómo guardar un grafo en la computadora. En una hoja es fácil, lo dibujamos y listo. Pero y en la compu? | ||
| Línea 48: | Línea 48: | ||
| Entonces, si las aristas del grafo no tienen información, y lo importante es si la arista existe (si el nodo $i$ está unido al $j$), podemos guardar un $1$ si la arista existe, y un $0$. Por ejemplo así: | Entonces, si las aristas del grafo no tienen información, y lo importante es si la arista existe (si el nodo $i$ está unido al $j$), podemos guardar un $1$ si la arista existe, y un $0$. Por ejemplo así: | ||
| - | {{ :algoritmos-oia:matriz-de-adyacencia.png?200 |}} | + | {{ :algoritmos-oia:matriz-de-adyacencia.png?300 |}} |
| Línea 63: | Línea 63: | ||
| Para cada nodo, vamos a guardar una lista con los nodos unidos a él. Si las aristas tuvieran longitud, podemos guardar en vez de los números de nodos, pares de enteros, que indiquen el nodo unido y la longitud de la arista que los une. | Para cada nodo, vamos a guardar una lista con los nodos unidos a él. Si las aristas tuvieran longitud, podemos guardar en vez de los números de nodos, pares de enteros, que indiquen el nodo unido y la longitud de la arista que los une. | ||
| - | {{ :algoritmos-oia:listas-de-adyacencia.png?200 |}} | + | {{ :algoritmos-oia:listas-de-adyacencia.png?300 |}} |
| - | Se implementa también como un vector de 2 dimensiones, $vector< vector<int> > grafo(n)$, que en el vector $grafo[i]$ están todos los nodos que están unidos al nodo $i$ a través de aristas. | + | Se implementa también como un vector de 2 dimensiones, $vector< vector<int> > grafo(n)$, pero de manera tal que en el vector $grafo[i]$ están todos los nodos que están unidos al nodo $i$ a través de aristas. |
| - | **Ventaja importante**: La complejidad especial es $O(n+m)$! Tenemos $n$ listas, pero en ellas aparecen exactamente todos los nodos entre los cuales hay aristas. Con la matriz de adyacencia también guardábamos información si no había arista, ahora si no hay arista simplemente no aparecen en la lista. | + | **Ventaja importante**: La complejidad espacial es $O(n+m)$! Tenemos $n$ listas, pero en ellas aparecen exactamente todos los nodos entre los cuales hay aristas. Con la matriz de adyacencia también guardábamos información si no había arista, ahora si no hay arista simplemente no aparecen en la lista. |
| **Desventaja**: Saber si exista una arista entre $i$ y $j$ implica recorrer toda la lista de $i$ y ver si está $j$, cuya complejidad es $O(n)$. | **Desventaja**: Saber si exista una arista entre $i$ y $j$ implica recorrer toda la lista de $i$ y ver si está $j$, cuya complejidad es $O(n)$. | ||
| - | === Por qué casi siempre se usa la manera de las listas de adyacencia? === | + | === ¿Por qué es más común utilizar las listas de adyacencia? === |
| Porque lo que más vamos a querer hacer es **recorrer un grafo**, entonces más que saber si existe una arista entre dos, querríamos "movernos a través de ella", y para eso, desde un nodo, queremos encontrar todas las aristas con un extremo en él, entonces mirar todos los nodos (matriz de adyacencia) es más caro que mirar únicamente los que sabemos que está unidos a él. | Porque lo que más vamos a querer hacer es **recorrer un grafo**, entonces más que saber si existe una arista entre dos, querríamos "movernos a través de ella", y para eso, desde un nodo, queremos encontrar todas las aristas con un extremo en él, entonces mirar todos los nodos (matriz de adyacencia) es más caro que mirar únicamente los que sabemos que está unidos a él. | ||
| Para ver más sobre recorrer grafos y problemas típicos, pueden ver las técnicas típicas que son [[algoritmos-oia/grafos/bfs|BFS]] y [[algoritmos-oia/grafos/dfs|DFS]]. | Para ver más sobre recorrer grafos y problemas típicos, pueden ver las técnicas típicas que son [[algoritmos-oia/grafos/bfs|BFS]] y [[algoritmos-oia/grafos/dfs|DFS]]. | ||
| + | |||
| + | No obstante, es bueno mencionar que las matrices de adyacencia funcionan y siempre podrían utilizarse, aunque el programa podría ser potencialmente muy lento (cuando $n^2$ sea mucho mayor que $m$). Si la complejidad no es un inconveniente, suele ser más cómodo usar matriz de adyacencia para todo. | ||
| + | |||
| + | === Grafo implícito === | ||
| + | |||
| + | Una última representación que vale la pena mencionar es la de grafo "implícito". En este caso, en realidad lo que hacemos es **no representar** al grafo directamente en memoria. Es decir, no guardamos todos los nodos y todas las aristas, sino que "sabemos" cuáles son, por las características del grafo. Esto depende de cada problema, pero cuando el grafo es algo en particular, suele ser lo más cómodo, sobre todo cuando el grafo es algo que nosotros como programadores decidimos, y no algo que se recibe directamente desde la entrada. | ||
| + | |||
| + | Por ejemplo, supongamos que vamos a trabajar con un grafo que tiene como nodos los números del 1 al 100. Además, sabemos que el grafo tiene una propiedad clave: dos nodos solamente son vecinos, cuando la diferencia entre sus números es 2, 3 o 7. Si bien podríamos armar toooda la matriz de adyacencia, o toooda la lista de adyacencia de este grafo, en este caso es más fácil directamente no crear esos datos, y directamente usar "la forma del grafo" para saber qué aristas hay. | ||
| + | |||
| + | Por ejemplo, la matriz de adyacencia se usa accediendo a posiciones $(i,j)$ para ver si hay arista entre $i$ y $j$. En nuestro ejemplo, en lugar de usar una matriz, para ver si hay arista entre $i$ y $j$ podemos simplemente hacer la diferencia ''abs(j-i)'', y ver si es 2, 3 o 7 para decidir allí mismo si hay arista. Esto podría programarse incluso en una función, ''hayArista(int i,int j)'', que funcionaría como si fuera la matriz de adyacencia, pero sin tener que armarla. | ||
| + | |||
| + | 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 ===== | ||
| Línea 96: | Línea 112: | ||
| Y estas son las únicas dos situaciones posibles, ya que si no empezamos desde un nodo sino desde el medio de una arista, y vamos desde ahí hacia un nodo, luego vamos a tener que hacer la otra parte de la arista y obviamente si podemos, podemos también empezar desde uno de estos nodos y terminar el mismo con el mismo camino. | Y estas son las únicas dos situaciones posibles, ya que si no empezamos desde un nodo sino desde el medio de una arista, y vamos desde ahí hacia un nodo, luego vamos a tener que hacer la otra parte de la arista y obviamente si podemos, podemos también empezar desde uno de estos nodos y terminar el mismo con el mismo camino. | ||
| - | Entonces, sabemos que es condición necesaria que haya $2$ ó $0$ nodos que estén en una cantidad impar de aristas. Puede verse, pensando en esto de "salir" y "entrar" del nodo que es una condición necesaria. | + | Entonces, sabemos que es condición necesaria que haya $2$ ó $0$ nodos que estén en una cantidad impar de aristas. Puede verse, pensando en esto de "salir" y "entrar" del nodo que es una condición suficiente. |
| Esto de "a cuántas aristas pertenece un nodo" se llama el **grado** de un nodo, y puede verse junto con otras definiciones [[algoritmos-oia/grafos/definiciones|acá]]. | Esto de "a cuántas aristas pertenece un nodo" se llama el **grado** de un nodo, y puede verse junto con otras definiciones [[algoritmos-oia/grafos/definiciones|acá]]. | ||
| - | Entonces, si vamos a tener un grafo de $n$ nodos, numerados del $0$ al $n-1$, y $m$ aristas, que nos las darán con dos enteros $u$, $V$ representando a los nodos que une cada arista, podemos chequear los grafos y si la figura puede dibujarse sin levantar el lápiz con este código: | + | Entonces, si vamos a tener un grafo de $n$ nodos, numerados del $0$ al $n-1$, y $m$ aristas, que vendrán dadas mediante dos enteros $u$, $v$ representando a los nodos que une cada arista, podemos verificar si la figura que el grafo representa puede dibujarse sin levantar el lápiz con este código: |
| <code cpp> | <code cpp> | ||
algoritmos-oia/grafos.1514891811.txt.gz · Última modificación: 2018/01/02 11:16 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
