Adjacency List Representation of Graph in C++
An Adjacency List is a common way to represent a graph in computer science. Specifically, it’s a way of representing a graph as a map from vertices to lists of edges. The adjacency list representation of a graph is linked to the degree of the vertices, and hence is quite space efficient. It only uses space proportional to the number of edges, which can be much less than the square of the number of vertices (which is the space complexity of the adjacency matrix representation).
Rules to Create Adjacency List of a Graph
- Create a list of n elements, where n is the number of vertices.
- For an undirected graph, add vertex j to the list of vertex i and add vertex i to the list of vertex j if there is an edge between i and j.
- For a directed graph, add vertex j to the list of vertex i if there is an edge from vertex i to vertex j.
- For a weighted graph, add a tuple (j, weight) to the list of vertex i to represent an edge from i to j with the given weight.
- If there is a self-loop on vertex i, add i to the list of vertex i (or (i, weight) if weighted).
Following these rules, we can create the adjacency list:
C++ Program to Implement a Graph Using Adjacency List
Approach
- Create a Graph class with a map of list named adjList that will be the adjacency list for the graph.
- The adjList will be of the type <int, list<int>>.
- The first data member of the adjList will represent a node and the second data member will be a linked list that will represent the list of nodes that have connection with the node.
- Implement an addEdge(u,v) method to add edges between the u and v vertex of the graph. If u and v are valid:
- Add vertex v to the adjacency list of vertex u.
- Add vertex u to the adjacency list of vertex v as this is an undirected graph.
- Implement a method print() to iterate through the adjacency list and print each vertex along with it’s connected vertices.
The following program illustrates how we can implement a graph using adjacency list in C++:
// C++ Program to Implement a Graph Using Adjacency List
#include <iostream>
#include <list>
#include <map>
using namespace std;
class Graph {
map<int, list<int> >
adjList; // Adjacency list to store the graph
public:
// Function to add an edge between vertices u and v of
// the graph
void add_edge(int u, int v)
{
// Add edge from u to v
adjList[u].push_back(v);
// Add edge from v to u because the graph is
// undirected
adjList[v].push_back(u);
}
// Function to print the adjacency list representation
// of the graph
void print()
{
cout << "Adjacency list for the Graph: " << endl;
// Iterate over each vertex
for (auto i : adjList) {
// Print the vertex
cout << i.first << " -> ";
// Iterate over the connected vertices
for (auto j : i.second) {
// Print the connected vertex
cout << j << " ";
}
cout << endl;
}
}
};
int main()
{
// Create a graph object
Graph g;
// Add edges to create the graph
g.add_edge(1, 0);
g.add_edge(2, 0);
g.add_edge(1, 2);
// Print the adjacency list representation of the graph
g.print();
return 0;
}
Output
Adjacency list for the Graph: 1 -> 2 3 2 -> 1 4 6 4 6 3 -> 1 5 5 4 -> 2 2 5 -> 3 3 6 -> 2 2
Time Complexity: O(V+E), where V is the number of vertices in the graph and E is the number of edges in the graph.
Auxiliary Space: O(V+E)
Implementation of Graph in C++
In C++, graphs are non-linear data structures that are used to represent the relationships between various objects. A graph is defined as a collection of vertices and edges. In this article, we will learn how to implement the graph data structure in C++.
Contact Us