[ Data Structures with Java ] Section 26.1 : Representing Graphs

Preface : 
In order to implement a graph, we need some way to represent the set of vertices and their edges. Assume the vertices are v0, v1, v2..., vm-1. An m by m matrix, called an adjacency matrix, identifies the edges. An entry in row i and column j corresponds to the edge e(v, vj). Its value is the weight of the edge, or 0 if the edge does not exist. For instance, below figure shows a non-weighted and a weighted graph, with the corresponding adjacency matrices : 
 

The adjacency matrix representation has the disadvantage that, regardless of the number of edges, it always requites V x V = V^2 entries, where V is the number of vertices. Another representation of a graph associates with each vertex a list of its adjacent vertices (neighbors). This model is often more efficient because it stores information for precisely the edges that actually belong to the graph. For each vertex, an element in the adjacency list is a pair consisting of the destination vertex and the weight of the edge. For the graph from upper figure, we give the adjacency-list representation as below figure : 
 

The DiGraph class uses the adjacency-list representation for a graph. We will discuss more about DiGraph in the follow up sections.