Search⌘ K
AI Features
Home
Courses
Mastering Graph Algorithms

Adjacency Matrix

Explore how adjacency matrices are used to represent graphs as two-dimensional arrays, capturing connections between vertices. Learn the properties of adjacency matrices for simple and non-simple graphs, including symmetry, row and column sums, and how these relate to vertex degrees. Understand the significance of matrix definitions for loops and multiple edges to better work with graph algorithms.

We'll cover the following...

We have already defined graphs in set-theoretic termsAs a set of vertices and a set of edges and represented them pictorially to impart intuition. However, we need an alternate representation that facilitates working with graphs algorithmically.

One such representation is the adjacency matrix representation. Using this representation, graphs can be stored as two-dimensional arrays.

Adjacency matrix for a simple graph

An adjacency matrix AA for a simple graphRecall that a graph is simple if it has at most one edge between a pair of vertices and if it has no loops. on nn vertices is an n×nn\times n matrix having the following properties:

  1. The ithi^{th} row and ithi^{th} column are associated with the same vertex, say viv_i.
  2. The value ai,ja_{i,j}
...