The adjacency list structure
are communication connections between pairs of computers on the Internet. The computers and the connections between them in a single domain, like wiley.com, form a subgraph of the Internet. If this subgraph is connected, then two users on computers in this domain can send e-mail to one another without having their information packets ever leave their domain. Suppose the edges of this subgraph form a spanning tree. This implies that, if even a single connection goes down (for
example, because someone pulls a communication cable out of the back of a
computer in this domain), then this subgraph will no longer be connected.There are a number of simple properties of trees, forests, and connected graphs.
We leave the justification of this proposition as an exercise (C-13.2).
13.1.1 The Graph ADT
edges():
Return an iterable collection of all the edges of the graph.
797
endVertices(e):
Return an array storing the end vertices of edge e.insertEdge(v, w,x):
Insert and return a new undirected edge with end vertices v and w and storing element x.removeVertex(v):
Remove vertex v and all its incident edges and return the element stored at v.
798