Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

AdjacencyMatrix: Representing a Graph by a Matrix

Explore how to represent graphs using an adjacency matrix, implement basic graph operations like adding and checking edges, and analyze the efficiency and memory trade-offs of this method. Understand the role of adjacency matrices in graph algorithms and how they support constant time edge queries for dense graphs.

We'll cover the following...

An adjacency matrix is a way of representing an n vertex graph G=(V,E)G = (V,E) by an n×nn \times n matrix, a, whose entries are boolean values.

C++
int n;

boolean[][] a;

AdjacencyMatrix(int n0) {

    n = n0;

    a = new T * [n];

}

The matrix entry a[i][j] is defined as

a[i][j]={true   if (i,j)∈Efalse   otherwise a[i][j] = \begin{cases} true & \ \ \ \text{if $(i,j)\in E$} \\ false & \ \ \ \text{otherwise} \end{cases}\ ...