One of the easiest ways to implement a graph is to use a two-dimensional matrix. In this matrix implementation, each of the rows and columns represent a vertex in the graph. The value that is stored in the cell at the intersection of row $$v$$ and column $$w$$ indicates if there is an edge from vertex $$v$$ to vertex $$w$$. When two vertices are connected by an edge, we say that they are adjacent. Figure 3 illustrates the adjacency matrix for the graph in Figure 2. A value in a cell represents the weight of the edge from vertex $$v$$ to vertex $$w$$.
The adjacency matrix is a good implementation for a graph when the number of edges is large. But what do we mean by large? How many edges would be needed to fill the matrix? Since there is one row and one column for every vertex in the graph, the number of edges required to fill the matrix is $$|V|^2$$. A matrix is full when every vertex is connected to every other vertex. There are few real problems that approach this sort of connectivity. The problems we will look at in this chapter all involve graphs that are sparsely connected.