Adjacency Matrix Representation of Graph
Formal Definition of a Graph
A graph G is defined as an ordered pair G=(V,E), where:
V is a set of vertices (also called nodes or points).
E is a set of edges (also called links or lines), where each edge connects a pair of vertices.
For example:
If V={A,B,C,D} and E={(A,B),(B,C),(C,D)}, then G=(V,E) represents a graph with 4 vertices and 3 edges.
Definition of Adjacency Matrix
An adjacency matrix for a graph G=(V,E) is a 2D array A of size ∣V∣×∣V∣, where:
∣V∣ is the number of vertices in the graph.
Each entry A[i][j] represents whether there is an edge between vertex i and vertex .
For an unweighted graph:
A[i][j]=1 if there is an edge between i and .
A[i][j]=0 if there is no edge between and .
For a weighted graph:
A[i][j]=weight of the edge if there is an edge between i and .
A[i][j]=∞ or some sentinel value (e.g.,
0or-1) if there is no edge.
Example: Representing a Graph Using Adjacency Matrix
Let’s consider a simple undirected, unweighted graph with 4 vertices V={A,B,C,D} and the following edges:
A is connected to B and C.
B is connected to A and D.
C is connected to A and D.
D is connected to B and C.
The graph can be visualized as:
A -- B
| \ |
| \ |
C -- DStep 1: Assign Indices to Vertices
For simplicity, assign indices to the vertices:
A=0
B=1
C=2
D=3
Step 2: Initialize the Adjacency Matrix
Create a 4×4 matrix initialized to 0:
A(0) 0 0 0 0 B(1) 0 0 0 0 C(2) 0 0 0 0 D(3) 0 0 0 0
Step 3: Fill the Matrix
For each edge (u,v), set A[u][v]=1 and A[v][u]=1 (since the graph is undirected):
Edge A−B: A[0][1]=1 , A[1][0]=1
Edge A−C : A[0][2]=1 , A[2][0]=1
Edge B−D : A[1][3]=1 , A[3][1]=1
Edge C−D : A[2][3]=1 , A[3][2]=1
Step 4: Final Adjacency Matrix
A(0) B(1) C(2) D(3) A(0) 0 1 1 0 B(1) 1 0 0 1 C(2) 1 0 0 1 D(3) 0 1 1 0
