Representation of Graphs

Ways to Represent a Graph

Here are the two most common ways to represent a graph :

1. Adjacency Matrix
2. Adjacency List

$$$$

Adjacency Matrix

The adjacency matrix is a two-dimensional matrix where each cell can contain a 0 or 1. The row and column headings represent the vertices.

If a cell contains 1, there exists an edge between the corresponding vertices, e.g., $Matrix[0][1]=1$ shows that an edge exists between vertex 0 and 1.

Explanation:

Initially, the whole matrix is initialized with 0’s, and as soon as we get an edge, we record the source (row) and destination (col) value inside our adjacency matrix.

Undirected Graph:

In the figure above, there is an undirected graph. If there exists an edge from the source to the destination, then we insert 1 for both cases ([row][col] and [col][row]) as we can traverse both ways.

Directed Graph:

In the case of a directed graph–which has an edge going from Node 0 to Node 1–, there is 1 for rowcol[0][1] in the adjacency matrix, and we similarly fill all the remaining parts of the matrix. If there is a node going from [row] to a [col], then we insert 1 for that particular [row][col]; otherwise, we put 0.

$$$$

2. Adjacency List

An array of Linked Lists is used to store edges between two vertices. The size of the array is equal to the number of vertices. Each index in this array represents a specific vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.

Undirected Graph: #

For the undirected graph shown above, each edge connected to a vertex is mentioned in the linked list of the array index (representing that vertex). Since there is an edge from vertex 0 to vertex 1, so the linked list of vertex 0 (at array index 0) has a node with value 1. Thus representing that vertex 1 is having an edge with vertex 0.

A significant point to note here is that since this is an undirected graph, a linked list of vertex 1 will also contain a node with value 0, thus representing a vertex from 1 to 0.

Directed Graph:

For the directed graph shown above, there are two outgoing edges from vertex 0: first to vertex 1 and second to vertex 2. So the linked list at array index 0 has nodes with value 1 and value 2.

Since this is a directed graph and edges are unidirectional, hence no edge exists between vertex 1 and vertex 0 and vertex 2 and vertex 0. Therefore 0 does not exist in a linked list of vertex 1 and vertex 2.