Given an undirected or a directed graph, implement graph data structure in C++ using STL. Implement for both weighted and unweighted graphs using Adjacency List representation of the graph.
Prerequisite: Terminology and Representations of Graphs
As we already know that adjacency list associates each vertex in the graph with the collection of its neighboring vertices or edges i.e every vertex stores a list of adjacent vertices. There are many variations of adjacency list representation depending upon the implementation.
For example, below is adjacency list representation of above graph –
Above representation allows the storage of additional data on the vertices but practically very efficient when the graph contains only few edges. We will use STL vector class to implement Adjacency List representation of a graph.
1. Directed Graph implementation using STL –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> #include <vector> using namespace std; // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // construct a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) { // insert at the end adjList[edge.src].push_back(edge.dest); // Uncomment below line for undirected graph // adjList[edge.dest].push_back(edge.src); } } }; // print adjacency list representation of graph void printGraph(Graph const& graph, int N) { for (int i = 0; i < N; i++) { // print current vertex number cout << i << " --> "; // print all neighboring vertices of vertex i for (int v : graph.adjList[i]) cout << v << " "; cout << endl; } } // Graph Implementation using STL int main() { // vector of graph edges as per above diagram. // Please note that initialization vector in below format will // work fine in C++11, C++14, C++17 but will fail in C++98. vector<Edge> edges = { { 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 }, { 3, 2 }, { 4, 5 }, { 5, 4 } }; // Number of nodes in the graph int N = 6; // construct graph Graph graph(edges, N); // print adjacency list representation of graph printGraph(graph, N); return 0; } |
Output:
0 –> 1
1 –> 2
2 –> 0 1
3 –> 2
4 –> 5
5 –> 4
2. Weighted Directed Graph implementation using STL –
We know that in a weighted graph, every edge will have a weight or cost associated with it as shown below:
Below is C++ implementation of a weighted directed graph using STL. The implementation is similar to above implementation of unweighted directed graph, except here we’ll also store the weight of every edge in the adjacency list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <vector> using namespace std; // data structure to store graph edges struct Edge { int src, dest, weight; }; typedef pair<int, int> Pair; // class to represent a graph object class Graph { public: // construct a vector of vectors of Pairs to represent an adjacency list vector<vector<Pair>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the vector to N elements of type vector<Pair> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) { int src = edge.src; int dest = edge.dest; int weight = edge.weight; // insert at the end adjList[src].push_back(make_pair(dest, weight)); // Uncomment below line for undirected graph // adjList[dest].push_back(make_pair(src, weight)); } } }; // print adjacency list representation of graph void printGraph(Graph const &graph, int N) { for (int i = 0; i < N; i++) { // print all neighboring vertices of given vertex for (Pair v : graph.adjList[i]) cout << "(" << i << ", " << v.first << ", " << v.second << ") "; cout << endl; } } // Graph Implementation using STL int main() { // vector of graph edges as per above diagram. // Please note that initialization vector in below format will // work fine in C++11, C++14, C++17 but will fail in C++98. vector<Edge> edges = { // (x, y, w) -> edge from x to y having weight w { 0, 1, 6 }, { 1, 2, 7 }, { 2, 0, 5 }, { 2, 1, 4 }, { 3, 2, 10 }, { 4, 5, 1 }, { 5, 4, 3 } }; // Number of nodes in the graph int N = 6; // construct graph Graph graph(edges, N); // print adjacency list representation of graph printGraph(graph, N); return 0; } |
Output:
(0, 1, 6)
(1, 2, 7)
(2, 0, 5) (2, 1, 4)
(3, 2, 10)
(4, 5, 1)
(5, 4, 3)
Note – We will follow above STL representation of graph as standard for all graph-related problems.
See more:
1. Graph Implementation in C++ without using STL
3. Graph Implementation in Java using Collections
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
nice work
simple and concise
int N = 6
What if there are 7 vertices? What if there are 1002 vertices? Is it a good practice to fix the value of N beforehand?
One of the reasons I prefer techiedelight is because of it’s high-quality solutions which is lacking in other websites. For instance, the code will run despite the
const&in line number 44, but it’s good coding practice. However, I don’t think fixing the values beforehand is good at all. Please correct me if I am wrongHi Abhishek,
We’re really glad you liked techiedelight and thanks for sharing your concerns.
The graph is the scariest topic for most students, and that was the main reason we have tried to keep the implementation simple by using few hard-coded values.
Happy coding 🙂
Thanks for the reply sir. With all due respect, we can’t use this code in competitive programming or even in the coding round of company interviews.
Please provide an alternate solution without any hard-coded values. If not anything, an ideone link at the end of the article would do.
Thanks again 🙂
Thanks Abhishek. You can use below implementation for coding round –
https://ideone.com/2WOwlF
Let us know if you have any more concerns. Happy coding 🙂
That was so generous of you. Thanks a lot 🙂
if you uncomment the line to support undirected graph, then you will find the output is incorrect. Some vertices will be duplicate output.
Thanks for sharing your concerns. Since there are duplicated edges in the input ({1, 2}, {2, 1} and {4, 5}, {5, 4}), there will be duplicates in the output. The program will return correct output on valid input.
But we can always add a condition to check for an edge to avoid inserting it again in the graph.
Well done! 🙂
Here is a generic implementation of the Graphs in C++ using STL https://github.com/sureshprakash/Graph-Library