Graph Representations: Adjacency List, Adjacency Matrix, and Attributes
Graph Representations: Adjacency List, Adjacency Matrix, and Attributes
A graph can be represented mainly in two ways:
- Adjacency-list representation
- Adjacency-matrix representation
Both representations can be used for directed and undirected graphs, and both can also be extended to represent weighted graphs and other graph attributes.
The choice of representation is important because it directly affects the space requirement and running time of graph algorithms.
1. Adjacency-List Representation
An adjacency-list representation maintains a list of vertices adjacent to each vertex.
For every vertex u, we maintain:
Adj[u]which contains all vertices v such that
Example
Consider the undirected graph:
2 / \ 1---3 | 4
The adjacency lists can be represented as:
Adj[1] → 2 → 3 → 4 Adj[2] → 1 → 3 Adj[3] → 1 → 2 Adj[4] → 1
Notice that because the graph is undirected, every edge appears twice.
For example, edge (1,2) appears in:
Adj[1]
and
Adj[2]
Directed Graph
For a directed graph:
1 → 2 ↓ 3
we have:
Adj[1] → 2 → 3 Adj[2] → NULL Adj[3] → NULL
Here, an edge (1,2) appears only in Adj[1].
Therefore, for a directed graph:
For an undirected graph:
2. Why Is Adjacency List Significant?
The major advantage is space efficiency.
The representation requires:
memory.
This is particularly important for sparse graphs.
A sparse graph has relatively few edges compared with the maximum possible number of edges.
For example, suppose:
but
An adjacency list stores only the existing edges.
It does not need to store information about all possible pairs of vertices.
3. Adjacency List and Graph Traversal
Adjacency lists are particularly suitable for algorithms such as:
- BFS
- DFS
- Connected components
- Topological sorting
- Strongly connected components
- Dijkstra's algorithm
- Prim's algorithm
- Kruskal's algorithm
For example, BFS needs to examine the neighbors of each vertex.
With an adjacency list, we directly obtain:
Adj[u]
and examine only the actual neighbors of u.
This is why BFS and DFS typically have running time:
Θ(V+E)when the graph is represented using adjacency lists.
4. Disadvantage of Adjacency Lists
Suppose we want to answer:
Does the edge (u,v) exist?
With an adjacency list, we have to search:
Adj[u]
for v.
Therefore, there is no constant-time edge lookup in the standard adjacency-list representation.
If u has many neighbors, the search may take:
O(deg(u))time.
This is one of the main reasons to use an adjacency matrix when rapid edge-existence testing is important.
5. Adjacency-Matrix Representation
An adjacency matrix represents a graph using a V × V matrix.
Let the matrix be:
A = (aᵢⱼ)
For an unweighted graph:
aᵢⱼ = 1 if the edge (i, j) exists aᵢⱼ = 0 otherwise
Example
Consider the graph:
1 --- 2 | | | | 3 --- 4
The adjacency matrix is:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |
For example:
A[1][2] = 1
means that there is an edge between vertices 1 and 2.
Similarly:
A[1][4] = 0
means that there is no edge between vertices 1 and 4.
Example
Consider:
1 --- 2 | | | | 3 --- 4
The adjacency matrix could be:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |
For example:
means there is an edge between 1 and 2.
While:
means there is no edge between 1 and 4.
6. Major Advantage of Adjacency Matrix
The biggest advantage is fast edge lookup.
To determine whether edge (u,v) exists, simply examine:
A[u][v]This takes:
Θ(1)time.
This is much faster than searching an adjacency list.
7. Disadvantage of Adjacency Matrix
An adjacency matrix always contains:
V²
entries, regardless of the actual number of edges.
Therefore, its space requirement is:
Θ(V²)
For example, if:
V = 10,000
then the matrix contains:
10,000² = 100,000,000
entries.
This can consume a large amount of memory even if the graph contains relatively few edges.
Therefore, adjacency matrices can be inefficient for sparse graphs.
8. Sparse vs Dense Graphs
This is the most important factor when choosing between the two representations.
Sparse Graph
A graph is sparse when:
E << V²
That is, the number of edges is much smaller than the maximum possible number of edges.
For sparse graphs, an adjacency list is usually preferred because it requires:
Θ(V + E)
space.
Dense Graph
A graph is dense when:
E is close to V²
For dense graphs, an adjacency matrix can be appropriate because:
Θ(V + E) ≈ Θ(V²)
In addition, the adjacency matrix provides constant-time edge lookup.
9. Comparison
|
|---|
10. Weighted Graphs
Both representations can also represent weighted graphs.
Suppose we have:
A ----5---- B \ / 2 3 \ / C
The numbers represent edge weights.
Weighted Adjacency List
Instead of storing only the neighboring vertex, store:
(neighbor, weight)
For example:
Adj[A] → (B,5) → (C,2) Adj[B] → (A,5) → (C,3) Adj[C] → (A,2) → (B,3)
Thus the weight is stored along with the corresponding edge.
Weighted Adjacency Matrix
Instead of storing 0/1, store the weight:
| A | B | C | |
|---|---|---|---|
| A | — | 5 | 2 |
| B | 5 | — | 3 |
| C | 2 | 3 | — |
If an edge does not exist, we can use an appropriate value such as NIL, ∞, or another value depending on the algorithm.
For shortest-path algorithms, using ∞ for "no edge" is often convenient.
11. Representation of Graph Attributes
Graph algorithms often need to maintain additional information about vertices and edges.
CLRS refers to these as attributes.
For a vertex v, an attribute can be written as:
v.dFor an edge (u,v), an attribute can be written as:
(u,v).fExample: BFS
During BFS, we may maintain attributes such as:
color distance parent
For a vertex u:
u.color u.d u.π
For example:
u.d = 3
means that the distance of vertex u from the BFS source is 3.
12. Example of Vertex Attributes
Suppose we have:
A / \ B C
During BFS starting from A, we might maintain:
| Vertex | Color | Distance | Parent |
|---|---|---|---|
| A | BLACK | 0 | NIL |
| B | BLACK | 1 | A |
| C | BLACK | 1 | A |
These attributes are not part of the graph's connectivity representation itself.
They are additional information maintained by the algorithm while processing the graph.
13. Example: DFS Attributes
DFS maintains attributes such as:
- color
- discovery time
- finishing time
- parent
For a vertex u:
u.dcan represent its discovery time, and
u.fcan represent its finishing time.
For example:
| Vertex | Discovery | Finish |
|---|---|---|
| A | 1 | 6 |
| B | 2 | 3 |
| C | 4 | 5 |
These attributes help DFS solve problems such as:
- cycle detection
- topological sorting
- strongly connected components
14. Where Are Attributes Stored?
There is no single best implementation for storing attributes.
One simple implementation is to use separate arrays.
Suppose vertices are numbered:
1,2,…,VWe can have:
Adj[1], Adj[2], ..., Adj[V]
and separate attribute arrays:
color[1 ... V] distance[1 ... V] parent[1 ... V]
Then:
color[u]
represents the color of vertex u,
distance[u]
represents its distance,
and
parent[u]
represents its parent.
15. Object-Oriented Representation
In an object-oriented implementation, we could instead define a Vertex object:
Vertex ---------------- id color distance parent
and perhaps an Edge object:
Edge ---------------- source destination weight
Then the graph consists of collections of these objects.
This is often more natural in languages such as Java, C++, or Python.
16. Why Are Attributes Important?
The graph representation tells us:
What connections exist in the graph?
The attributes tell us:
What information the algorithm has discovered or is maintaining about those connections and vertices.
For example, in Dijkstra's algorithm:
distance[v]
stores the current best-known distance from the source to v.
In BFS:
distance[v] parent[v]
help construct shortest paths in an unweighted graph.
In DFS:
discovery[v] finish[v] parent[v]
help identify structural properties of the graph.
17. The Main Significance
The choice of graph representation is not merely a programming detail. It directly influences algorithmic efficiency.
A useful way to remember it is:
GRAPH | How should it be stored? | +-----------+-----------+ | | Adjacency List Adjacency Matrix | | Sparse graphs Dense graphs | | Θ(V + E) space Θ(V²) space | |Efficient traversal Fast edge lookup
And on top of either representation, we can maintain:
Vertex Attributes + Edge Attributes
These attributes provide the information needed by individual graph algorithms.
Summary
Adjacency lists are generally the representation of choice for sparse graphs because they use space and allow graph traversals to run in time. Adjacency matrices require Θ(V²) space but provide constant-time testing of whether a particular edge exists, making them attractive for dense graphs or algorithms that require frequent edge lookups. Both representations can be extended to store edge weights and other vertex and edge attributes required by graph algorithms.
Comments
Post a Comment