Search⌘ K
Home
Courses
Data Structures with Generic Types in Java

AdjacencyMatrix: Representing a Graph by a Matrix

Explore how an adjacency matrix represents a graph with boolean values in Java. Understand how to add, remove, and check edges efficiently. Learn the trade-offs in memory and performance, especially for dense graphs, and see how matrix operations relate to graph properties like path lengths.

We'll cover the following...

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

Java
int n;

boolean[][] a;

AdjacencyMatrix(int n0) {

  n = n0;

  a = new boolean[n][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}\ ...