En papel, un grafo se puede representar dibujando una imagen en la que los vértices se representan con puntos y las aristas con líneas ó flechas, o podemos representarlo haciendo una lista de los vértices y aristas.

Ahora bien, para su representación como estructura, veremos que para representar grafos en un programa de computadora, se pueden utilizar también dos formas:

Representación de matriz de adyacencia

Podemos representar G con una matriz A = (a¡j) de n X n elementos, llamada matriz de adyacencia de G. A está definida por:

a¡j = 1 si vivj ∈ E para 1 <= i,j <= n

a¡j = 0 para los demás casos

La matriz de adyacencia de un grafo no dirigido es simétrica (y sólo es preciso almacenar la mitad). Si G = (V, E, W) es un grafo ponderado, los pesos se podrán almacenar en la matriz de adyacencia modificando su definición como sigue:

a¡j = W(vivj) si vivj ∈ E para 1 <= i,j <= n

a¡j = c para los demás casos

donde c es una constante cuyo valor depende de la interpretación de los pesos y del problema a resolver. Si los pesos se ven como costos, se podría escoger ∞ (o algún número muy alto) para c porque el costo de recorrer una arista inexistente es prohibitivamente alto.

Los algoritmos para resolver algunos problemas de grafos requieren examinar y procesar de alguna manera cada una de las aristas por lo menos una vez. Si se usa una representación de matriz de adyacencia, podríamos imaginar que un grafo tiene aristas entre todos los pares de vértices distintos, porque muchos algoritmos examinarían cada elemento de la matriz para determinar cuáles aristas existen.

Puesto que el número de posibles aristas es n^2 en un grafo dirigido, o de n(n — 1)/2 en un grafo no dirigido, la complejidad de tales algoritmos estará en Ω(n^2).

Representación con arreglo de listas de adyacencia

Una alternativa respecto a la representación con matriz de adyacencia es un arreglo indizado por número de vértice, que contiene listas ligadas llamadas listas de adyacencia. Por cada vértice vi, el ¡-ésimo elemento del arreglo contiene una lista con información acerca de todas las aristas de G que "salen de" vi. En un grafo dirigido esto implica que vi es la cola de la arista; en un grafo no dirigido, la arista incide en vi. La lista de v¡ contiene un elemento por arista. Para precisar la explicación, llamemos al arreglo infoAdya, que podría definirse así:

Lista[] infoAdya = new Lista[n+1];

Usaremos los índices 1, ..., n, así que reservaremos espacio para n + 1 posiciones y no usaremos la posición 0. Ahora infoAdya [ i ] será una lista con información acerca de las aristas que salen de vi.
La ventaja de una estructura de listas de adyacencia es que las aristas que no existen en G no existen tampoco en la representación.

Ya sean grafos dirigidos o no dirigidos, no habrá campo peso, puesto que infoAdya se ha reducido a un solo campo. Cada elemento j de la lista indica la presencia de la arista vivj en G.

Ejemplo:

Debido al tipo de datos abstracto (TDA) podemos incluir en la arista el costo, para el caso de tratarse de grafos ponderados, además, podemos definir en la clase una lista que contenga los nombres de los vértices y otro que contenga la lista de aristas del grafo, cada nodo tiene su propia lista de adyacentes. En un grafo no dirigido cada arista se representa dos veces; es decir, si vw es una arista, hay un elemento para w en la lista de adyacencia para v y un elemento para v en la lista de adyacencia para w.

Conceptualmente, para un grafo ponderado se tiene como ejemplo: