Graph Representation by Adjacency List

June 27, 2023

Adjacency List using Linked list

There are many ways to represent a graph. Two of the most famous ways are Adjacency matrix and Adjacency list. We can represent a Graph by creating the Adjacency list using an array linked lists for all the possible nodes.

We will take integers as nodes, so an array of linked lists will work. In the array, the linked list in ith index will denote the list of nodes that can be arrived directly from the node i.

Graph Representation by Adjacency List | PrepInsta

Explanation

Prerequisites : What is a Graph?

Let us say we have 6 nodes, and they are 0,1,2,3,4,5 respectively. And There are 7 edges, in between the following nodes : (1,2), (2,3), (1,0), (1,5), (5,2), (5,4), (0,3). So,

from node 0, we can directly visit the nodes namely 1, 3.
from node 1, we can directly visit the nodes namely 0, 2, 5.
from node 2, we can directly visit the nodes namely 1, 3, 5.
from node 3, we can directly visit the nodes namely 0, 2.
from node 4, we can directly visit the node namely 5.
from node 5, we can directly visit the nodes namely 1, 2, 4.

So if we now see the array of the linked list, it will be like, [(1, 3), (0, 2, 5), (1, 3, 5), (0, 2), (5), (1, 3, 4)].

Implementing by this way will help us using different algorithms to sove graph theory problems, like DFS, BFS, etc.

Use of STL in C++ for Graph Representation by Adjacency List

In C++, if we use standard template library, we can get in built implemented data structures for Linked lists. Mostly we can use vector or list datatype. In this case, you can use a vector for the sake of understanding. So we have to take an array of this vector, say Adj[], where all the elements of the array are vectors themselves.

We have to first declare the array of vector, by, vector Adj[v]
Where v is the number of vertices, here say 6.
Then we will create a function that will take two integers as argument and add those two nodes with each other, i.e, void AddNodes(int a, int b).

Here is the code that implements the graph previously mentioned

#include <bits/stdc++.h>
using namespace std;
 
void Addedges(int a,int b, vector<int> *Adj) // TO add two nodes
{
    Adj[a].push_back(b);
    Adj[b].push_back(a);
}
 
int main()
{
    int v=6; // Declaring number of vertices
    vector<int> Adj[v]; // Declaring the adjacency list
    Addedges(1,2,Adj); // Adding Edges
    Addedges(2,3,Adj);
    Addedges(1,0,Adj);
    Addedges(1,5,Adj);
    Addedges(5,2,Adj);
    Addedges(5,4,Adj);
    Addedges(0,3,Adj);
    // Now we will take the output :
    for(int i=0;i<v;i++){cout<<“From Node “<<i<<” We can visit: “;
    for(int j=0;j<Adj[i].size();j++)
    cout<<Adj[i][j]<<“, “;
    cout<<endl;
    }
}

Output :

From Node 0 We can visit: 1, 3,
From Node 1 We can visit: 2, 0, 5,
From Node 2 We can visit: 1, 3, 5,
From Node 3 We can visit: 2, 0,
From Node 4 We can visit: 5,
From Node 5 We can visit: 1, 2, 4,

Want to traverse the graph? Here is how to DFS Traverse a graph