Quote:
I looked into Google and came across incidence list and adjacency list representation
|
I would suggest ignoring the "Incidence List" article in wikipedia, which complicates the data structure (my suspicion is that the article was added to promote the book that it references; edge oriented adjacency lists have been around since at least the 1970s).
However, it is worth reading the
adjacency list and
adjacency matrix articles.
The simplest representation is an array of pairs, where each pair structure contains the vertices of a single edge. This is effectively a list of edges. However, this representation is slow for many applications such as traversals, because it is hard to find the next vertices as you traverse the graph.
An adjacency matrix is a two dimensional array, which contains the connection between each pair of vertices. In other words, each index combination represents two vertices, and the value of the array is the edge cost; vertices that are not connected will have a dummy value at that point of the array (eg 0). An adjacency matrix is fast for
some applications (though not for traversal). And for graphs where the number of edges is significantly less than the number of vertices squared, it wastes a lot of storage.
An adjacency list is an array of vertices, where each array entry has a list of other vertices adjacent to that vertex. It is an efficient way of storing all the data, and allows easy traversal of the graph, so it is a reasonable structure for your application.
Your example (undirected) graph:
Code:
|--------------31
| |
| 2-----4----6-----8
| |
|----5-----13---\
| 19
12-----27---/
|
28
For your example, the adjacency list would look like this:
Code:
2: 4, 5
4: 2, 6
5: 2, 12, 13, 31
6: 4, 8, 31
8: 6
12: 5, 27
13: 5, 19
19: 13, 27
27: 12, 19, 28
28: 27
31: 5, 6
and the adjacency matrix like this:
Code:
2 4 5 6 8 12 13 19 27 28 31
2 1 1
4 1 1
5 1 1 1 1
6 1 1 1
8 1
12 1 1
13 1 1
19 1 1
27 1 1 1
28 1
31 1 1