**Q:** In the graph implementation
presented in this chapter, why is a linked list used for the list of
adjacency-list structures but sets are used for the adjacency
lists?

**A:** Many adjacency-list
representations of graphs consist of an array of adjacency lists, with
each element in the array corresponding to one vertex in the graph.
The implementation in this chapter deviates from this model. First, it
uses a linked list in place of the array because the list can
dynamically expand and contract as we insert and remove vertices.
Second, it uses sets for the adjacency lists because the vertices they
contain are not ordered, and the primary operations associated with
adjacency lists (inserting and removing vertices, and testing for
membership) are well-suited to the set abstract datatype presented
earlier. Perhaps the list of adjacency-list structures could have been
implemented using a set as well, but this was ruled out because the
primary operation here is to locate the adjacency lists of specific
vertices. A linked list is better suited to this than a set.

**Q:** Suppose we model an
internet using a graph (as shown earlier in this chapter) and we
determine that the graph contains an articulation point. What are the
implications of this?

**A:** Graphs have many important
uses in network problems. If in a graph modeling an internet we
determine that there is an articulation point, the articulation point
represents a single point of failure. Thus, if a system residing at ...

Start Free Trial

No credit card required