Adjacency Matrix

Adjacency Matrix is a way of representing a graph using a 2D array. It is particularly useful for dense graphs where the number of edges is close to the maximum number of edges.

Going back to a previous undirected graph example, we can represent this as a matrix:

$$A_{directed}=\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

They are defined as follows:

Let G = (V, E) with |V| = n and vertices indexed v_1, …, v_n. The adjacency matrix A ∈ ℝ^{n×n} is defined by:

• Directed, unweighted graphs:

  $$A_{ij}=\{\begin{array}{ll}1& \text{if }(v_i,v_j)\in E,\\ 0& \text{otherwise.}\end{array}$$

• Undirected, unweighted graphs:

  $$A_{ij}=\{\begin{array}{ll}1& \text{if }\{v_i,v_j\}\in E,\\ 0& \text{otherwise,}\end{array}\text{so }{A}_{ij}=A_{ji}.$$

  For simple graphs (no self-loops), A_{ii} = 0.

• Weighted graphs:

  $$A_{ij}=\{\begin{array}{ll}w(v_i,v_j)& \text{if an edge exists between }{v}_i\text{ and }{v}_j,\\ 0\text{ (or }+\infty \text{/}\perp \text{ by convention)}& \text{otherwise.}\end{array}$$

  For undirected weighted graphs, A is symmetric. In multigraphs, A_{ij} may store the number of parallel edges (or the sum of their weights).