In order for a graph with N vertices (nodes) to be connected, it needs
at least N-1 edges. While no stipulations are made about the
connectedness of the graphs here, it can be assumed that the number of
edges (relative to the number of nodes) for both examples is toward
the low end.
In this sense an adjacency list might be considered the more suitable,
because of the economy of storage, esp. in the first example.
An adajcency matrix will require N by N entries, each a zero or one.
An adjacency list contains a number of node pairs equal to the number
of edges. It can be easily seen that when the number of edges is
roughly equal to N, the storage of N^2 numbers (zero or one). An
adjacency list with about N entries will be smaller (except perhaps
for small values N and using "bits" to store the matrix entries, which
probably makes it tedious to "lookup" information).
On the other hand, if the speed of lookup is sufficiently critical,
the costs of extra storage incurred by the adjacency matrix might be
reasonable. Checking for adjacency using the adjacency list need not
be terribly slow or expensive; if the nodes can be linearly ordered,
then a binary search can be done to check adjacency in O(ln N) time.
However the lookup cost for the adjacency matrix is essentially a
constant, ie. O(1) time.
Tradeoffs in "space" and "time" are a staple of software design. What
I'm reading into the qualification of the second part of this problem
is that while space would be saved by using an adjacency list, the
adjacency matrix is more suitable because the time savings is of
greater importance.
regards, mathtalk-ga |
