An undirected graph need not explicitly store two separate directed edges to represent a single undirected edge. An alternative would be to store only a single undirected edge (I, J) to connect Vertices I and J. However, what if the user asks for edge (J, I)? We can solve this problem by consistently storing the edge such that the lesser of I and J always comes first. Thus, if we have an edge connecting Vertices 5 and 3, requests for edge (5, 3) and (3, 5) both map to (3, 5) because 3

Looking at the adacency matrix, we notice that only the lower triangle of the array is used. Thus we could cut the space required by the adjacency matrix from jVj2 positions to jVj(jVj-1)=2 positions. Read Section 12.2 on triangular matrices. The reimplement the adjacency matrix representation of Figure 11.6 to implement undirected graphs using a triangular array.

Transcribed Image Text:

class Graphm implements Graph { // Graph: Adjacency matrix // The edge matrix // Number of edges // The mark array private int [] [] matrix; private int numEdge; public int [] Mark; public Graphm () {} public Graphm (int n) { Init (n); } public void Init (int n) { Mark = new int [n]; } matrix = new int [n] [n]; numEdge = 0; public int n() { return Mark.length; } // # of vertices public int e() { return numEdge; } // # of edges public int first (int v) { // Get v's first neighbor for (int i=0; i