properties of graphs

|V| = number of vertices

|E| = number of edges

a graph with $V$ vertices has at most $\frac{V(V-1)}{2}$ edges

if $E$ is closer to $V^2$, the graph is dense

if $E$ is closer to $V$, the graph is sparse

whether a graph is dense or sparse will influence the ideal choice for implementing the graph

graph representations

graph implementations

three main possible graph implementations

  1. array of edges — expressing a graph as a list of vertex-vertex pairs
  2. adjacency matrix — edges defined by present value in V*V matrix
  3. adjacency list — edges defined by entries in array of V lists

1. array-of-edges

simply storing an array of vertex pairs (possible an array of structs of node pairs)

e.g. [ (0,1), (1,2), (1,3), (2,3) ]

if the graph is a directed graph, the ordering of vertices within an edge pair denote direction

e.g. (1,2) means edge from 1 to 2, while (2,1) means edge from 2 to 1

properties