---

Representation of Graphs

Adjacency Matrix

• Adjacency matrix is a way to represent a graph.
• It shows which nodes are adjacent to one another.
• Graph is represented using a square matrix.
• Graph can be divided into two categories:
a. Sparse Graph

b. Dense Graph

a. Sparse graph

Sparse graph contains less number of edges.

b. Dense graph

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.
• Adjacency matrix of an undirected graph is always a symmetric matrix which means an edge (i, j) implies the edge (j, i).

• The above graph represents undirected graph with the adjacency matrix representation. It shows adjacency matrix of undirected graph is symmetric. If there is an edge (2, 4), there is also an edge (4, 2).

• Adjacency matrix of a directed graph is never symmetric adj[i][j] = 1, indicated a directed edge from vertex i to vertex j.

• The above graph represents directed graph with the adjacency matrix representation. It shows adjacency matrix of directed graph which is never symmetric. If there is an edge (2, 4), there is not an edge (4, 2). It indicates direct edge from vertex i to vertex j.

Advantages of Adjacency Matrix

• Adjacency matrix representation of graph is very simple to implement.
• Adding or removing time of an edge can be done in O(1) time. Same time is required to check, if there is an edge between two vertices.
• It is very convenient and simple to program.

Disadvantages of Adjacency Matrix

• It consumes huge amount of memory for storing big graphs.
• 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.

Adjacency List

• Adjacency list is another representation of graphs.
• It is a collection of unordered list, used to represent a finite graphs.
• Each list describes the set of neighbors of a vertex in the graph.
• Adjacency list requires less amount of memory.
• For every vertex, adjacency list stores a list of vertices, which are adjacent to the current one.
• In adjacency list, an array of linked list is used. Size of the array is equal to the number of vertices.

• In adjacency list, an entry array[i] represents the linked list of vertices adjacent to the i^th vertex.
• Adjacency list allows to store the graph in more compact form than adjacency matrix.
• It allows to get the list of adjacent vertices in O(1) time.

Disadvantages of Adjacency List

• It is not easy for adding or removing an edge to/from adjacent list.
• It does not allow to make an efficient implementation, if dynamically change of vertices number is required.

Important Note:

Vertex: Each node of the graph is represented as a vertex.
Edge: It represents a path between two vertices or a line between two vertices.
Path: It represents a sequence of edges between the two vertices.
Adjacency: If two nodes or vertices are connected to each other through an edge, it is said to be an adjacency.

---