Previous    Next

This figure depicts a representation of the graph in Screenshot as an array of linked lists. The space used is proportional to the number of nodes plus the number of edges. To find the indices of the vertices connected to a given vertex v, we look at the vth position in an array, which contains a pointer to a linked list containing one node for each vertex connected to v. The order in which the nodes appear on the lists depends on the method that we use to construct the lists.

The implementation in Programs 17.9 and 17.10 is a low-level one. An alternative is to use a Java collection class to implement each edge list (see Exercise 17.30). The disadvantage of doing so is that such implementations typically support many more operations than we need and therefore typically carry extra overhead that might affect the performance of all of our algorithms (see Exercise 17.31). Indeed, all of our graph algorithms use the Graph ADT interface, so this implementation is an appropriate place to encapuslate all the low-level operations and concentrate on efficiency without affecting our other code. Another advantage of using the linked-list representation is that it provides a concrete basis for understanding the performance characteristics of our implementations.

This implementation of the interface in Program 17.1 uses an array of linked lists, one corresponding to each vertex. It is equivalent to the representation of Program 3.17, where an edge v-w is represented by a node for w on list v and a node for v on list w. Implementations of remove and edge are omitted, because our use of singly-linked lists does not accommodate constant-time implementations of these operations (adding them for clients that do not need fast implementations is a straightforward exercise (see Exercise 17.28)). The insert code keeps insertion time constant by not checking for duplicate edges, and the total amount of space used is proportional to V + E. This representation is most suitable for sparse multigraphs.

```class Graph // sparse multigraph implementation
{
private int Vcnt, Ecnt;
private boolean digraph;
private class Node
{ int v; Node next;
Node(int x, Node t) { v = x; next = t; }
}
Graph(int V, boolean flag)
{
Vcnt = V; Ecnt = 0; digraph = flag;
}
int V() { return Vcnt; }
int E() { return Ecnt; }
boolean directed() { return digraph; }
void insert(Edge e)
{ int v = e.v, w = e.w;
Ecnt++;
}
// Program 17.10
}
```

This implementation of the iterator for Program 17.9 maintains a link t to traverse the linked list associated with vertex v. An invocation of beg() followed by a sequence of invocations of nxt() (checking that end() is false before each invocation) gives a sequence of the vertices adjacent to v in G.

```AdjList getAdjList(int v)
{
private int v;
private Node t;
{ this.v = v; t = null; }
public int beg()
return t == null ? -1 : t.v; }
public int nxt()
{ if (t != null) t = t.next;
return t == null ? -1 : t.v; }
public boolean end()
{ return t == null; }
}
```

#### Exercises

17.27 Show, in the style of Screenshot, the adjacency-lists structure produced when you use Program 17.9 to insert the edges in the graph

(in that order) into an initially empty graph.

Provide implementations of remove and edge for the adjacency-lists graph class (Program 17.9). Note: Duplicates may be present, but it suffices to remove any edge connecting the specified vertices.

17.30 Modify the adjacency-lists implementation of Programs 17.9 and 17.10 to use a Java collection instead of an explicit linked list for each adjacency list.

Run empirical tests to compare your Graph implementation of Exercise 17.30 with the implementation in the text. For a well-chosen set of values for V, compare running times for a client program that builds complete graphs with V vertices, then extracts the edges using Program 17.2.

17.32 Give a simple example of an adjacency-lists graph representation that could not have been built by repeated insertion of edges by Program 17.9.

How many different adjacency-lists representations represent the same graph as the one depicted in Screenshot?

17.34 Add a method to the graph ADT (Program 17.1) that removes self-loops and parallel edges. Provide the trivial implementation of this method for the adjacency-matrix–based class (Program 17.7), and provide an implementation of the method for the adjacency-list–based class (Program 17.9) that uses time proportional to E and extra space proportional to V.

Write a version of Program 17.9 that disallows parallel edges (by scanning through the adjacency list to avoid adding a duplicate entry on each edge insertion) and self-loops. Compare your implementation with the implementation described in Exercise 17.34. Which is better for static graphs? Note: See Exercise 17.49 for an efficient implementation.

Write a client of the graph ADT that returns the result of removing self-loops, parallel edges, and degree-0 (isolated) vertices from a given graph. Note: The running time of your program should be linear in the size of the graph representation.

• 17.37 Write a client of the graph ADT that returns the result of removing self-loops, collapsing paths that consist solely of degree-2 vertices from a given graph. Specifically, every degree-2 vertex in a graph with no parallel edges appears on some path u-...-w where u and w are either equal or not of degree 2. Replace any such path with u-w, and then remove all unused degree-2 vertices as in Exercise 17.36. Note: This operation may introduce self-loops and parallel edges, but it preserves the degrees of vertices that are not removed.

17.38 Give a (multi)graph that could result from applying the transformation described in Exercise 17.37 on the sample graph in Screenshot.

 Previous    Next