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.
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.
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.
| Alice | Bob | Charlie | Diana | |
|---|---|---|---|---|
| Alice | 0 | 1 | 0 | 1 |
| Bob | 1 | 0 | 1 | 0 |
| Charlie | 0 | 1 | 0 | 1 |
| Diana | 1 | 0 | 1 | 0 |
An adjacency list consists of a list of nodes, where each node points to a list of its adjacent nodes.
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.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 1 |
| C | 1 | 0 | 0 | 1 | 0 |
| D | 0 | 1 | 1 | 0 | 0 |
| E | 0 | 1 | 0 | 0 | 0 |
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.
| Math 101 | Physics 101 | Chemistry 101 | Biology 101 | |
|---|---|---|---|---|
| Math 101 | 0 | 1 | 0 | 0 |
| Physics 101 | 0 | 0 | 1 | 1 |
| Chemistry 101 | 0 | 0 | 0 | 1 |
| Biology 101 | 0 | 0 | 0 | 0 |
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.