How to implement a graph

Let's take the edit distance example graph from an earlier post.

This is our example graph:


An edge exists between two nodes if they differ by only one letter.

There are two main ways of representing graphs in memory:

1. Adjacency Matrix

This is a 2x2 matrix with a bit set if there is an edge between two vertices. Note that because this is a undirected graph this matrix will be symmetrical.

       cat    cab    car    bar    tar    tat
cat             1       1
cab   1                1
car    1       1                1  
bar                      1                1
tar                                1              1
tat                                          1

2. Adjacency List

For each Vertex maintain a list containing all linked vertices.

cat      [cab, car]
cab     [cat, car]
car      [cat, bar, cab]
bar      [car, tar]
tar       [bar, tat]
tat       [tar]

(Note that to solve the problem, it's a simple matter of building a graph and executing dijkstra's algorithm to find the shortest path between two nodes.)