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++.
Implementation of Graph Data Structure in C++
There are two primary ways to implement or represent graph data structures in C++:
- Using Adjacency Matrix
- Using Adjacency List
Let us consider the following undirected graph:
Adjacency Matrix Representation of Graph in C++
An adjacency matrix is a square matrix (2D vector in C++) used to represent a finite graph. It provides a straightforward way to describe the relationships between nodes (vertices) in a graph.
Rules to Create Adjacency Matrix of a Graph
- Create an n x n 2d vector named matrix, where n is the number of vertices, with all entries initialized to 0.
- For an undirected graph, set both matrix[i][j] and matrix[j][i] to 1 if there is an edge between vertices i and j.
- For a directed graph, set matrix[i][j] to 1 if there is an edge from vertex i to vertex j.
- For a weighted graph, set matrix[i][j] to the weight of the edge between vertices i and j.
- If there is a self-loop on vertex i, set matrix[i][i] to 1 (or the weight if weighted).
From the above rules, we can create the adjacency matrix:
C++ Program to Implement a Graph Using Adjacency Matrix
The following program illustrates how we can implement a graph using an adjacency matrix in C++:
// C++ Program to Implement a Graph Using Adjacency Matrix
#include <iostream>
#include <vector>
using namespace std;
class Graph {
// Adjacency matrix to store graph edges
vector<vector<int> > adj_matrix;
public:
// Constructor to initialize the graph with 'n' vertices
Graph(int n)
{
adj_matrix
= vector<vector<int> >(n, vector<int>(n, 0));
}
// Function to add an edge between vertices 'u' and 'v'
// of the graph
void add_edge(int u, int v)
{
// Set edge from u to v
adj_matrix[u][v] = 1;
// Set edge from v to u (for undirected graph)
adj_matrix[v][u] = 1;
}
// Function to print the adjacency matrix representation
// of the graph
void print()
{
// Get the number of vertices
cout << "Adjacency Matrix for the Graph: " << endl;
int n = adj_matrix.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << adj_matrix[i][j] << " ";
}
cout << endl;
}
}
};
int main()
{
// Number of vertices
int n = 4;
// Create a graph with 4 vertices
Graph g(n);
// Adding the specified edges in the graph
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(1, 3);
g.add_edge(2, 3);
// Print the adjacency matrix representation of the
// graph
g.print();
return 0;
}
Output
Adjacency Matrix for the Graph: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
Time Complexity: O(V^2), where V is the number of vertices in the graph.
Auxiliary Space: O(V^2)
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)
Difference Between the Adjacency Matrix and Adjacency List
Aspect | Adjacency Matrix | Adjacency List |
---|---|---|
Memory Usage | Requires O(V^2) space | Requires O(V + E) space |
Edge Existence Query | Quick O(1) check | O(degree(v)) check for adjacency of v |
Space Efficiency | Inefficient for sparse graphs | Efficient for sparse graphs |
Adding/Removing Edges | O(1) for adding/removing edges | Depends on data structure, typically O(1) |
Iterating Over Edges | Inefficient, potentially O(V^2) for traversal | Efficient, O(V + E) for traversal |
Suitability | Suitable for dense graphs | Suitable for sparse graphs |
Related Articles
You can also go through the following articles to improve your understanding about the graph data structure:
Contact Us