Graph Representation: Matrix vs List Examples

Graph representation is crucial in computer science, mathematics, and various applications, as it provides a way to model relationships between entities. Two common methods for representing graphs are the adjacency matrix and the adjacency list. This article presents three practical examples that highlight the differences between these two representations.

Example 1: Social Network Connections

In a social network, each user can be thought of as a node, and connections between users (friendships) as edges. Let’s consider a small network of four users: Alice, Bob, Charlie, and Diana.

Adjacency Matrix Representation

An adjacency matrix is a 2D array where the rows and columns represent nodes. A value of 1 indicates an edge between the corresponding nodes, while a value of 0 indicates no edge.

Adjacency List Representation

An adjacency list consists of a list of nodes, where each node points to a list of its adjacent nodes.

• Alice: [Bob, Diana]
• Bob: [Alice, Charlie]
• Charlie: [Bob, Diana]
• Diana: [Alice, Charlie]

Notes

• The adjacency matrix is easier to implement and understand for small graphs.
• The adjacency list is more space-efficient, especially for larger graphs with many nodes and fewer edges.

Example 2: City Road Network

Consider a simplified model of a city road network with five intersections: A, B, C, D, and E. Roads connecting these intersections can be represented as a graph.

Adjacency Matrix Representation

Adjacency List Representation

• A: [B, C]
• B: [A, D, E]
• C: [A, D]
• D: [B, C]
• E: [B]

Notes

• The adjacency matrix makes it straightforward to check if a direct road exists between any two intersections.
• The adjacency list provides quicker access to all roads connected to a specific intersection.

Example 3: Course Prerequisites

In a university setting, courses can be represented as nodes, and prerequisites as directed edges. Let’s analyze four courses: Math 101, Physics 101, Chemistry 101, and Biology 101.

Adjacency Matrix Representation

Adjacency List Representation

• Math 101: [Physics 101]
• Physics 101: [Chemistry 101, Biology 101]
• Chemistry 101: [Biology 101]
• Biology 101: []

Notes

• The adjacency matrix allows for easy identification of which courses require others as prerequisites.
• The adjacency list is more efficient for queries related to the prerequisite paths of a specific course.

In conclusion, both adjacency matrices and adjacency lists have their own advantages and use cases. Understanding these representations can significantly enhance the way you analyze and solve problems related to graphs.