Graphs and Representing of Graphs

Graphs

•      We will typically express running times in terms of |E| and |V| (often dropping the |’s)

–     If |E| » |V|² the graph is dense

–     If |E| » |V| the graph is sparse

•      If you know you are dealing with dense or sparse graphs, different data structures may make sense

Representing Graphs

•      Assume V = {1, 2, …, n}

•      An adjacency matrix represents the graph as a n x n matrix A:

–     A[i, j]   = 1 if edge (i, j) Î E   (or weight of edge)
                        = 0 if edge (i, j) Ï E