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 a los vértices no por nombre (como "Audrey", "Boston", o "suéter") sino por un número. Es decir, típicamente numeramos los vertical bar, V, vertical bar vértices de 0 a vertical bar, V, vertical bar, minus, 1. Aquí está el grafo de la red social con sus 10 vértices identificados por números en lugar de nombres:
Grafo de una red social

Listas de aristas

Una forma sencilla de representar un grafo es solo una lista, o un arreglo, de vertical bar, E, vertical bar 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 Θ(E) \Theta(E) . Por ejemplo, aquí está cómo representamos una lista de aristas en JavaScript para el grafo de la red social:
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
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 vertical bar, E, vertical bar 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(lgE) O(\lg E) ? La respuesta es un poco complicada.

Matrices de adyacencia

Para un grafo con vertical bar, V, vertical bar vértices, una matriz de adyacencia es una matriz de vertical bar, V, vertical bar, times, vertical bar, V, vertical bar de ceros y unos, donde la entrada en la fila i y la columna j es 1 si y solo si la arista left parenthesis, i, comma, j, right parenthesis está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada de la fila 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:
Matriz de adyacencia
En JavaScript, representamos esta matriz como:
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
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 left parenthesis, i, comma, j, right parenthesis se encuentra en el grafo mirando graph[i][j]. ¿Así que cuál es la desventaja de una matriz de adyacencia? Dos cosas, en realidad. En primer lugar, ocupa un espacio Θ(V2) \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 vertical bar, V, vertical bar en la fila 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 de la fila i, columna j es 1 si y solo si la entrada de la fila j, columna i es 1. Para un grafo dirigido, la matriz de adyacencia no necesita ser simétrica.

Listas de adyacencia

Representar un grafo con listas de adyacencia combina las matrices de adyacencia con listas de aristas. Para cada vértice i, almacena un arreglo de los vértices adyacentes a él. Típicamente tenemos un arreglo de vertical bar, V, vertical bar 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:
Listas de adyacencia
En JavaScript, representamos estas listas de adyacencia como:
[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]
Los números de 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 left parenthesis, i, comma, j, right parenthesis está presente en el grafo, vamos a la lista de adyacencia de i en un tiempo constante y luego buscamos a j en la lista de adyacencia de i. ¿Cuánto tarda eso en el peor de los casos? La respuesta es Θ(d) \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 vertical bar, V, vertical bar, minus, 1 (si i es adyacente a todos los demás vertical bar, V, vertical bar, minus, 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 o 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 lista de adyacencia de un grafo en la variable graph, de modo que graph[i] es un arreglo que contiene a los vecinos del vértice i. Entonces, para llamar a una función doStuff en cada vértice adyacente al vértice i, podrías utilizar el siguiente código JavaScript:
for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}
Si la notación de doble subíndice te confunde, puedes pensarlo de esta manera:
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}
¿Cuánto espacio ocupan las listas de adyacencia? Tenemos vertical bar, V, vertical bar listas, y aunque cada lista podría tener hasta vertical bar, V, vertical bar, minus, 1 vértices, las listas de adyacencia para un grafo no dirigido en total contienen 2, vertical bar, E, vertical bar elementos. ¿Por qué 2, vertical bar, E, vertical bar? Cada arista left parenthesis, i, comma, j, right parenthesis 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 vertical bar, E, vertical bar aristas. Para un grafo dirigido, las listas de adyacencia contienen un total de vertical bar, E, vertical bar 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.