Graphs and Representations

G = ( V, E ) where V is vertices and E is edges

Two common graph representations:

1. Adjacency list. Good for sparse graphs and is generally preferred.

2. Adjacency matrix. Only reasonable when a graph is sparse.

A dense graph is when | E | ~ |V|² , a  sparse graph has | E | << | V |²

Adjacency-List Representation:

Adjacency is an array with | V | lists, one for each vertex." u Î V Adj[u] is the adjacency list for vertex u and points to all vertices v so that the edge ( u, v ) Î E. If G is a directed graph, then:

å u Î V  | Adj [u] | = | E |

If G is an undirected graph, then:

å u Î V

| Adj [u] | = 2 | E |

 

 

With the adjacency-list representation we have that:

 O ( max ( | V |, | E | )) = O ( | V | + | E | )

memory is required. This is as small as we can imagine if G does not have a special (computable) structure. If G is a weighted graph then for each f Î E we associate w_f. with the adjacency-list representation we merely store w_f in the Adj[u] corresponding to v where ( u, v ) = f, the edge in question. Many other graph variants are easily incorporated into the adjacency-lists representation.

Problem: Given edge ( u, v ) is it in the graph ?

Answer: Must search Adj[u] to see if v is there. If Adj[u] is really big, this can be searching the whole graph.

Solution: (Memory-speed trade off) Adjacency-Matrix representation. Assume that the vertices are numbered: 1, 2, ..., | V |. Associate with G the | V | x | V | matrix [A]_ij = a_ij so that a_ij = 1 if ( i, j ) Î E and 0 otherwise. This representation takes O (  | V |² ) memory whether G is sparse or dense! Clearly: ( u, v ) Î G ? can be answered in O ( 1 ) time!

If G is an undirected graph, then if ( i, j ) Î Gso is ( j, i ) thus we have: if a_ij = 1, a_ji = 1and if  a_ij = 0 then a_ji = 0, so a_ij = a_ji . [A^T]_ij =  a_ji , A^T is the transpose of A, swapping across a diagonal division of the matrix. In an undirected graph, A = A^T (symmetric) instead of "1" in A we can use w. If 0 is a valid weight, we must identify non-edges with another value: "nil".

Note: if a_ij = 0,1 we can store A in bit form very efficiently

Symmetric

non-symmetric or asymmetric