7.1.1 Data Structures for Graph Representation

Next: 7.2 Shortest Paths Problem Up: 7.1 Directed Graphs Previous: 7.1 Directed Graphs

1.: Adjacency Matrix: The matrix is of order (n x n) where n is the number of vertices. The adjacency matrix for the graph in Figure 7.2 is

$\displaystyle \left[\vphantom{\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{array}}\right.$ $\displaystyle \begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{array}$ $\displaystyle \left.\vphantom{\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{array}}\right]$
2.: Adjacency List: Figures 7.2 and 7.3 provide two different adjacency list representations for the graph of Figure 7.1

**Figure 7.2:** Adjacency list representation of the digraph
$\begin{figure} \centerline{\psfig{figure=figures/Fdigraph2.ps}} \end{figure}$

**Figure 7.3:** Adjacency list using cursors
$\begin{figure} \centerline{\psfig{figure=figures/Fdigraph3.ps}} \end{figure}$

eEL,CSA_Dept,IISc,Bangalore