December 02, 2019
Amitraj
Adjacency Matrix
1. Adjacency matrix is a way to represent a graph.
2. It shows which nodes are adjacent to one another.
3. Graph is represented using a square matrix.
Graph can be divided into two categories:
a. Sparse Graph
b. Dense Graph
a. Sparse graph contains less number of edges.
b. Dense graph contains number of edges as compared to sparse graph.
->Adjacency matrix is best for dense graph, but for sparse graph, it is not required.
->Adjacency matrix is good solution for dense graph which implies having constant number of vertices.
NOTE: Adjacency matrix of an undirected graph is always a symmetric matrix which means an edge (i, j) implies the edge (j, i).
NOTE: Adjacency matrix of a directed graph is never symmetric adj[i][j] = 1, indicated a directed edge from vertex i to vertex j.
Advantages of Adjacency Matrix
1. Adjacency matrix representation of graph is very simple to implement.
2. Adding or removing time of an edge can be done in O(1) time.
3. Same time is required to check, if there is an edge between two vertices.
4. It is very convenient and simple to program.
Disadvantages of Adjacency Matrix
1. It consumes huge amount of memory for storing big graphs.
2. It requires huge efforts for adding or removing a vertex. If you are constructing a graph in dynamic structure, adjacency matrix is quite slow for big graphs.
