Graph Representations: Adjacency Matrix vs. Adjacency List
Explore the two primary ways to represent graphs in C#: adjacency matrix and adjacency list. Understand their structure, benefits, and limitations. Learn when to use each method based on graph density, memory efficiency, and the nature of graph operations like traversal and edge lookup.
We'll cover the following...
A graph can be represented in memory in different ways. Two of the most common representations are the adjacency matrix and the adjacency list. Each representation has its own advantages and limitations, and the best choice depends on the graph and the problem we want to solve.
Adjacency matrix
An adjacency matrix uses a two-dimensional array, such as bool[,] or int[,] in C#, to represent connections between vertices. If a graph has n vertices, then the matrix has n by n cells. Each row and column corresponds to a vertex.
If there is an edge between two vertices, the corresponding cell stores a value such as 1 or true. If there is no edge, the cell stores 0 or false. This makes it easy to see which pairs of vertices are connected. ...