Representar grafos

Hay varias maneras de representar grafos, cada uno con sus ventajas y desventajas. Algunas situaciones, o algoritmos que queremos ejecutar que tengan grafos como entrada, requieren un representación, y otros requieren una representación diferente. Aquí, veremos tres formas de representar grafos.

Veremos tres criterios. Una es cuánta memoria, o espacio, necesitamos en cada representación. Usaremos notación asintótica para eso. ¡Sí, podemos usar notación asintótica para otros fines además de expresar tiempos de ejecución! En realidad es una forma de caracterizar funciones, y una función puede describir un tiempo de ejecución, una cantidad de espacio requerido, o algún otro recurso. Los otros dos criterios que usaremos se relacionan con el tiempo. Uno es cuánto se tarda en determinar si una arista dada está en el grafo. El otro es cuánto se tarda en encontrar los vecinos de un vértice dado.

Es común identificar los vértices no por nombre (como "Audrey", "Boston" o "suéter") sino por un número. Es decir, típicamente numeramos los $|V|$‍ vértices de 0 a $|V|-1$‍. Aquí está el grafo de la red social con sus 10 vértices identificados por números en lugar de nombres:

Una forma sencilla de representar un grafo es solo una lista, o un arreglo, de $|E|$‍ aristas, a la que llamamos una lista de aristas. Para representar una arista, solo tenemos un arreglo de dos números de vértices, o un arreglo de objetos que contienen los números de vértices sobre los que inciden las aristas. Si las aristas tienen pesos, agrega ya sea un tercer elemento al arreglo o más información al objeto, que dé el peso de la arista. Como cada arista contiene solo dos o tres números, el espacio total para una lista de aristas es $\mathrm{\Theta }(E)$‍. Por ejemplo, aquí está cómo representamos una lista de aristas en JavaScript para el grafo de la red social:

Las listas de aristas son sencillas, pero si queremos encontrar si el grafo contiene una arista en particular, tenemos que buscar en la lista de aristas. Si las aristas aparecen en la lista de aristas sin ningún orden en particular, eso es una búsqueda lineal sobre $|E|$‍ aristas. Pregunta para pensar al respecto: ¿cómo puedes organizar una lista de aristas para hacer que la búsqueda de una arista en particular tarde un tiempo $O(\lg E)$‍? La respuesta es un poco complicada.

Para un grafo con $|V|$‍ vértices, una matriz de adyacencia es una matriz de $|V|\times |V|$‍ de ceros y unos, donde la entrada en el renglón $i$‍ y la columna $j$‍ es 1 si y solo si la arista $(i,j)$‍ está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada del renglón $i$‍, columna $j$‍ y reserva un valor especial (tal vez null) para indicar una arista ausente. Aquí está la matriz de adyacencia para el grafo de la red social:

En JavaScript, representamos esta matriz como:

Con una matriz de adyacencia, podemos averiguar si una arista está presente en un tiempo constante, solo buscando la entrada correspondiente en la matriz. Por ejemplo, si la matriz de adyacencia se llama graph, entonces podemos consultar si la arista $(i,j)$‍ se encuentra en el grafo al mirar graph[i][j]. ¿Entonces cuál es la desventaja de una matriz de adyacencia? Dos cosas, en realidad. En primer lugar, ocupa un espacio $\mathrm{\Theta }(V^2)$‍, incluso si el grafo es disperso: relativamente pocas aristas. En otras palabras, para un grafo disperso, la matriz de adyacencia es en su mayoría 0s, y utilizamos mucho espacio para representar solo algunas aristas. En segundo lugar, si quieres averiguar cuáles vértices son adyacentes a un vértice dado $i$‍, tienes que mirar en todas las entradas $|V|$‍ en el renglón $i$‍, incluso si solo un pequeño número de vértices son adyacentes al vértice $i$‍.

Para un grafo no dirigido, la matriz de adyacencia es simétrica: la entrada del renglón $i$‍, columna $j$‍ es 1 si y solo si la entrada del renglón $j$‍, columna $i$‍ es 1. Para un grafo dirigido, la matriz de adyacencia no necesita ser simétrica.

Representar un grafo con listas de adyacencia combina las matrices de adyacencia con las listas de aristas. Para cada vértice $i$‍, almacena un arreglo de los vértices adyacentes a él. Típicamente tenemos un arreglo de $|V|$‍ listas de adyacencia, una lista de adyacencia por vértice. Aquí está una representación de una lista de adyacencia del grafo de la red social:

En JavaScript, representamos estas listas de adyacencia como:

Los números del vértice en una lista de adyacencia no están obligados a aparecer en ningún orden en particular, aunque a menudo es conveniente enumerarlos en orden ascendente, como en este ejemplo.

Podemos llegar a la lista de adyacencia de cada vértice en un tiempo constante, porque solo tenemos que indexar en un arreglo. Para averiguar si una arista $(i,j)$‍ está presente en el grafo, vamos a la lista de adyacencia de $i$‍ en un tiempo constante y luego buscamos $j$‍ en la lista de adyacencia de $i$‍. ¿Cuánto tarda eso en el peor de los casos? La respuesta es $\mathrm{\Theta }(d)$‍, donde $d$‍ es el grado del vértice $i$‍, porque eso es qué tan larga es la lista de adyacencia de $i$‍. El grado del vértice $i$‍ puede ser tan alto como $|V|-1$‍ (si $i$‍ es adyacente a todos los demás $|V|-1$‍ vértices) o tan bajo como 0 (si $i$‍ está aislado, sin aristas incidentes). En un grafo no dirigido, el vértice $j$‍ está en la lista de adyacencia del vértice $i$‍ si y solo si $i$‍ está en la lista de adyacencia de $j$‍. Si el grafo está ponderado, entonces cada elemento en cada lista de adyacencia es un arreglo de dos elementos o un objeto, que da el número de vértice y el peso de la arista.

Puedes usar un bucle for para iterar sobre los vértices en una lista de adyacencia. Por ejemplo, supón que tienes una representación de una lista de adyacencia de un grafo en la variable graph, de modo que graph[i] es un arreglo que contiene los vecinos del vértice $i$‍. Entonces, para llamar una función doStuff en cada vértice adyacente al vértice $i$‍, podrías utilizar el siguiente código JavaScript:

Si la notación de doble subíndice te confunde, puedes pensarlo de esta manera:

¿Cuánto espacio ocupan las listas de adyacencia? Tenemos $|V|$‍ listas, y aunque cada lista podría tener hasta $|V|-1$‍ vértices, las listas de adyacencia para un grafo no dirigido contienen $2|E|$‍ elementos en total. ¿Por qué $2|E|$‍? Cada arista $(i,j)$‍ aparece exactamente dos veces en las listas de adyacencia, una vez en la lista de $i$‍ y una vez en la lista de $j$‍, y hay $|E|$‍ aristas. Para un grafo dirigido, las listas de adyacencia contienen un total de $|E|$‍ elementos, un elemento por cada arista dirigida.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.