Adjacency Matrix Adjacency List
Adjacency List
Adjacency List consists of Linked Lists. Each vertex is considered an array index, and each element represents a linked list. These linked lists contain the vertices which have edges with the index vertex. Here’s an example of an adjacency list:
Let’s say a graph contains V number of vertices and E number of edges. Generally, the space complexity will be O(V + E). Worst-case space complexity will be O(V2) if the given Graph is the complete Graph
Adjacency Matrix
Adjacency Matrix composes of a 2D array. Graph having a V number of vertices, the size of the matrix will be VxV. Say, matrix[i][j] = 5. It means there’s an edge between node i and j where the weight is 5. Let’s look at the following Graph and its Adjacency matrix:
We created the 2D array using these steps: Step 1) Vertice A has a direct edge with B, and the weight is 5. So, the cell in row A and column B will be filled with 5. The rest of the cells in row A will be filled with zero. Step 2) Vertices B have a direct edge with C, and the weight is 4. So, the cell in row B and column C will be filled with 4. The remaining cells in row B will be filled with zero as B has no outgoing edge to any other nodes. Step 3) Vertices C have no direct edges with any other vertices. So, row C will be filled with zeros. Step 4) Vertice D has a directed edge with A and C.
Here, the cell in row D and column A will have a value of 7. Cells in row D and column C will have a value of 2. The rest of the cells in row D will be filled with zeros.
Step 5) Vertices E has a directed edge with B and D. The cell in row E and column B will have a value of 6. Cells in row E and column D will have a value of 3. The rest of the cells in row D will be filled with zeros. Here are some points to notice:
The Graph has no self-loops when the primary diagonal of the adjacency matrix is 0. The Graph is a directed graph if the indexes (a,b) and (b, a) don’t have the same value. Otherwise, the Graph is a directed graph. The Graph will be a weighted graph if the value of the cells is more than 1.
There’s some problem with the adjacency matrix as it requires squared spaces. Here, we are storing the edges that are not connected. These edges allocate space in the memory. For example, if we have a graph with 100 nodes, then 10 thousand cells are needed to store it in the RAM. With fewer edges in the Graph, allocating such large memory can be a waste. So, the space complexity using the Adjacency matrix will be O(N2), where N means the number of nodes in the Graph.
