Graph Representations

We want the internal representation of a graph to be one that can be efficiently manipulated.

If the external representation of a node is a string, such as a city name, we can use a Map or symbol table to map it to an internal representation such as:

• a node number, convenient to access arrays of information about the node

• a pointer to a node object.

A graph is called dense if |E| = O(|V|²); if |E| is less, the graph is called sparse .

All real-world graphs are sparse unless they are small.