Graph ADT: Efficiency of Operations
- Analyze and compare the complexity of basic operations for adjacency list vs. matrix-based representations of a graph.
Here is a summary of the core operations of Graph ADT:
| Operation | Description |
|---|---|
insert(v) | creates and returns a new Vertex storing element $v$ |
remove(V) | removes vertex $V$ and returns the element stored in it |
insert(V, U, e) | creates and returns a new Edge from vertex $V$ to $U$ (storing $e$) |
remove(E) | removes edge $E$ and returns element stored in it. |
vertices() | returns an iteration of all the vertices of the graph. |
edges() | returns an iteration of all the edges of the graph. |
outgoing(V) | returns an iteration of all outgoing edges of vertex $V$. |
incoming(V) | returns an iteration of all incoming edges of vertex $V$. |
Exercise Complete the following table. Describe the efficiency of each operation for the representation in that column.
Assume given a vertex, we can access it in an adjacency list or matrix (the index corresponding to it) in constant time.
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
insert(v) | ||
remove(V) | ||
insert(V, U, e) | ||
remove(E) | ||
vertices() | ||
edges() | ||
outgoing(V) | ||
incoming(V) |
Solution
The answers here entirely depend on how you implement each representation. Many of the assumptions made below are not described in the notes. You must refer to the recorded lecture for a more elaborate discussion.
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
insert(v) | $\Omicron(1)$ | $\Omicron(N^2)$ |
remove(V) | $\Omicron(1)$ | $\Omicron(N^2)$ |
insert(V, U, e) | $\Omicron(1)$ | $\Omicron(1)$ |
remove(E) | $\Omicron(\max(\deg(V),\deg(U)))^*$ | $\Omicron(1)$ |
vertices() | $\Omicron(1)$ | $\Omicron(1)^*$ |
edges() | $\Omicron(M)$ | $\Omicron(N^2)$ |
outgoing(V) | $\Omicron(\deg^{+}(V))$ | $\Omicron(N)$ |
incoming(V) | $\Omicron(\deg^{-}(V))$ | $\Omicron(N)$ |
-
remove(E)in adjacency list: if $E$ has the endpoints $V$ and $U$, we must find (linear search) and remove $E$ from the list of edges associated with $V$ and with $U$. -
vertices()in the adjacency matrix is $\Omicron(1)$ by keeping an explicit list in addition to the adjacency matrix representation.
In most cases, "Adjacency List" is preferred for efficient operations: especially if the operation involves "exploring" the graph.