# What Is Adjacency Matrix in Graph Data Structure?

//

Larry Thompson

In graph theory, an adjacency matrix is a square matrix used to represent a finite graph. It provides a concise way to represent the connections between the vertices of a graph. This article will explore what an adjacency matrix is, how it works, and its advantages and disadvantages.

## What is a Graph?

Before diving into adjacency matrices, let’s quickly understand what a graph is in the context of computer science. A graph is a data structure that consists of a set of vertices or nodes connected by edges or arcs. Graphs are widely used to represent various real-world applications such as social networks, transportation networks, and computer networks.

An adjacency matrix is a square matrix where the rows and columns represent the vertices of a graph. The element at position (i, j) in the matrix represents whether there exists an edge between vertex i and vertex j.

The adjacency matrix can be represented using various programming languages such as C++, Java, and Python. However, for the purpose of this tutorial, let’s focus on understanding its concept rather than implementation details.

### An Example

Consider the following undirected graph:

```    A -- B
/ \    \
/   \    \
C     D -- E
```

To create an adjacency matrix for this graph, we assign each vertex a unique number:

• A = 0
• B = 1
• C = 2
• D = 3
• E = 4

Now, let’s represent the above graph using an adjacency matrix:

```    | A | B | C | D | E |
------------------------
A   | 0 | 1 | 1 | 0 | 0 |
B   | 1 | 0 | 0 | 1 | 1 |
C   | 1 | 0 | 0 | 0 | 0 |
D   | 0 | 1 | 0 | 0 | 1 |
E   | 0 | 1 | 0 | 1 |
```

In the matrix, a value of 1 indicates the presence of an edge between two vertices, while a value of 0 indicates the absence of an edge. For example, in the above matrix, there is an edge between vertex A and vertex B (matrix[0][1] = 1) and no edge between vertex A and vertex D (matrix[0][3] = 0).

• Simplicity: The concept of adjacency matrices is relatively simple to understand.
• Ease of implementation: It is straightforward to implement an adjacency matrix in various programming languages.
• Efficient for dense graphs: Adjacency matrices are efficient for representing densely connected graphs.
• Ease of edge operations: Determining whether there is an edge between two vertices is a constant time operation (O(1)).