A little graph theory

Did some reading and discussion about graph theory. Briefly.

Agreed that the graph we are using is undirected, cyclic, planar (maybe? not important? or is?). Still wondering whether to use adjacency matrix, adjacency list or edge list representation.

adjacency matrix : amount of storage O(V2). Any edge can be accessed, added, or removed in O(1) time. To add or remove a vertex requires reallocating and copying the whole graph, an O(V2) operation.

adjacency list : only O(V + E) memory is required.Edge insertion is O(1), though accessing any given edge is O(alpha), where alpha is the sparsity factor of the matrix (which is equal to the maximum number of out-edges for any vertex in the graph).

edge list : The memory required is only O(E). Edge insertion is typically O(1), though accessing a particular edge is O(E) (not efficient).

Next to do: make some simple codes using templates.

Advertisements