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

• graphs can be represented in multiple ways — e.g. the same graph drawn in two different ways, or using node-node pairs to represent graphs

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