Adjacency List Implementation in C++.

In the previous posts, we covered the basics of graph data structure and how we use an adjacency matrix for its representation. Here we are going to learn how to represent graph data structure using Adjacency List.

Adjacency List.

An adjacency list is a way of representing a graph as an array of linked lists, where each vertex has a linked list of its adjacent vertices. In this representation, we create an array of sizes V (V is the number of vertices). Each index of the array will carry a different list which will contain the list of vertices connected to that particular index.

Adjacency List for an Undirected Graph.

In an undirected graph, each edge is bidirectional, meaning that if there's an edge from vertex u to vertex v, there's also an edge from v to u. Therefore, in the adjacency list representation of an undirected graph, we add both u to the adjacency list of v and v to the adjacency list of u.

Example: 

Adjacency List for Undirected Graph

C++ code Implementation of Adjacency List for the above-undirected graph:

//C++ Code for Printing Adjacency List of Undirected Graph
#include <iostream>
#include <vector>
using namespace std;

//Add edges to undirected graph
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

//printing the adjacency list
void printGraph(vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Adjacency list of vertex " << v << "->";
        for (auto u : adj[v])
            cout << u << " ";
        cout << endl;
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 3);
    printGraph(adj, V);
    return 0;
}

Output:

Adjacency list of vertex 0->1 2
Adjacency list of vertex 1->0 2 3
Adjacency list of vertex 2->0 1 3
Adjacency list of vertex 3->1 2

Adjacency List for a Directed Graph.

In a directed graph, each edge is unidirectional, meaning that there's an edge from vertex u to vertex v, but not necessarily from v to u. Therefore, in the adjacency list representation of a directed graph, we only add v to the adjacency list of u.

Example:

Adjacency List for Directed Graph

C++ code Implementation of Adjacency List for the above-directed graph:

//C++ Code for Printing Adjacency List of Directed Graph
#include <iostream>
#include <vector>
using namespace std;

//Add edges to directed graph
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
}

//printing the adjacency list
void printGraph(vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Adjacency list of vertex " << v << "->";
        for (auto u : adj[v])
            cout << u << " ";
        cout << endl;
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 1);
    printGraph(adj, V);
    return 0;
}

Output:

Adjacency list of vertex 0->1 2
Adjacency list of vertex 1->2
Adjacency list of vertex 2->3
Adjacency list of vertex 3->1

The Adjacency list is an efficient way to represent the graph when the graph is less dense but when the graph is dense we use the Adjacency matrix to represent a graph.