Adjacency Matrix in Graph Theory

---

In graph theory, an Adjacency Matrix is a square matrix used to represent a graph. It provides a way of encoding the structure of a graph, where each element of the matrix indicates whether pairs of vertices are adjacent (connected) or not in the graph. The adjacency matrix is a powerful and widely used representation for both directed and undirected graphs, making it suitable for various applications, such as finding shortest paths, connectivity, and performing graph traversal.

---

What is an Adjacency Matrix?

An Adjacency Matrix is a 2D array (or matrix) used to represent a graph. The size of the matrix is $V\times V$, where $V$ is the number of vertices in the graph. The elements of the matrix indicate whether a pair of vertices is connected by an edge.

For a graph with $V$ vertices, the adjacency matrix $A$ is an $V\times V$ matrix where:

• For undirected graphs, if there is an edge between vertices $u$ and $v$, then $A[u][v]=A[v][u]=1$ (or the weight of the edge if the graph is weighted).
• For directed graphs, if there is an edge from vertex $u$ to vertex $v$, then $A[u][v]=1$ (or the weight of the edge). If the edge is directed from $v$ to $u$, then $A[v][u]=1$.

Adjacency Matrix for an Undirected Graph

In an undirected graph, the adjacency matrix is symmetric, meaning if there's an edge between vertex $u$ and vertex $v$, the matrix has equal values at $A[u][v]$ and $A[v][u]$.

Example:

Consider the undirected graph:

    A - B
    |   |
    C - D

• Vertices: $A,B,C,D$
• Edges: $(A,B),(A,C),(B,D),(C,D)$

The adjacency matrix for this graph would look like this:

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

• $A[A][B]=1$, $A[B][A]=1$ (since there’s an edge between A and B)
• $A[A][C]=1$, $A[C][A]=1$ (since there’s an edge between A and C)
• Similarly, edges $(B,D)$ and $(C,D)$ are represented by 1 in the appropriate positions.

Adjacency Matrix for a Directed Graph

In a directed graph, the adjacency matrix is not necessarily symmetric. If there is an edge from vertex $u$ to vertex $v$, then only $A[u][v]=1$, and the reverse $A[v][u]$ remains 0 (unless there’s also an edge in that direction).

Example:

Consider the directed graph:

    A → B
    ↓   ↑
    C → D

• Vertices: $A,B,C,D$
• Edges: $(A,B),(A,C),(B,D),(C,D)$

The adjacency matrix for this directed graph would look like this:

	A	B	C	D
A	0	1	1	0
B	0	0	0	1
C	0	0	0	1
D	0	0	0	0

• $A[A][B]=1$ (edge from A to B)
• $A[A][C]=1$ (edge from A to C)
• $A[B][D]=1$ (edge from B to D)
• $A[C][D]=1$ (edge from C to D)

---

Advantages of Adjacency Matrix

1. Fast Edge Lookup: Checking if an edge exists between any two vertices is a constant-time operation, i.e., $O(1)$, because the matrix element at position $A[u][v]$ directly gives the information.
2. Simple Representation: The adjacency matrix is easy to implement and understand. It directly maps the structure of the graph.
3. Efficient for Dense Graphs: If the graph is dense (i.e., has a large number of edges), the adjacency matrix is efficient because it uses $O(V^2)$ space, where $V$ is the number of vertices, and all edge connections are explicitly stored.

---

Disadvantages of Adjacency Matrix

1. Space Complexity: The adjacency matrix requires $O(V^2)$ space, which can be inefficient for sparse graphs (graphs with fewer edges relative to the number of vertices).
2. Inefficient for Sparse Graphs: For sparse graphs, the adjacency matrix wastes a lot of space to represent the many non-existent edges.
3. Slower for Edge Enumeration: If you need to list all the neighbors of a vertex, it requires scanning the entire row, resulting in $O(V)$ time, which is less efficient than other representations like adjacency lists.

---

Operations on Adjacency Matrix

1. Check if an Edge Exists: To check if there is an edge from vertex $u$ to vertex $v$, simply check if $A[u][v]=1$ (or the edge weight if the graph is weighted). This operation takes $O(1)$ time.

2. Add an Edge: To add an edge from vertex $u$ to vertex $v$, set $A[u][v]=1$ (or the edge weight). This operation also takes $O(1)$ time.

3. Remove an Edge: To remove an edge between vertices $u$ and $v$, set $A[u][v]=0$. This operation also takes $O(1)$ time.

4. Get All Neighbors of a Vertex: To get all neighbors of a vertex $u$, scan the $u$-th row to find all columns $v$ where $A[u][v]=1$. This operation takes $O(V)$ time.

---

Adjacency Matrix in Python

Here’s how to represent a graph using an adjacency matrix in Python:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.matrix = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v):
        self.matrix[u][v] = 1  # For a directed graph
        # For undirected graph, also set matrix[v][u] = 1
        # self.matrix[v][u] = 1

    def remove_edge(self, u, v):
        self.matrix[u][v] = 0

    def display(self):
        for row in self.matrix:
            print(row)

# Example usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print("Adjacency Matrix of the Graph:")
g.display()

Output:

Adjacency Matrix of the Graph:
[0, 1, 1, 0]
[0, 0, 0, 1]
[0, 0, 0, 1]
[0, 0, 0, 0]

 

---

---