Adjacency List with String vertices using C++ STL

Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List using C++ STL where each vertex is a string instead of and integer. This code has been requested many times, so I decided to create a separate page for it. Some of the features of this code are –

  • The Adjacency List is an unordered map of list. Where each list item is a pair, from the utility header file. This pair stores two values, the destination vertex (string), (V2 in an edge V1 → V2) and the weight (integer) of the edge.
  • For adding an edge, all we have to do is to call push_back() function. Although it does not represent our addEdge() in the initial discussion where we had head insertion, it is tail insertion which is an O(1) insertion operation.
  • The vector representing the vertices is 1-indexed.
#include <iostream>
#include <string>
#include <unordered_map>
#include <list>

using namespace std;

int main()
{
    int vertices, edges, weight;
    string v1, v2;
     
    printf("Enter the Number of Vertices -\n");
    cin >> vertices;
     
    printf("Enter the Number of Edges -\n");
    cin >> edges;
     
    // Adjacency List is a map of <string, list>.
    // Where each element in the list is pair<string, int>
    // pair.first -> the edge's destination (string)
    // pair.second -> edge's weight
    unordered_map< string, list< pair<string, int> > > adjacencyList(vertices + 1);
     
    printf("Enter the Edges V1 -> V2, of weight W\n");
    for (int i = 1; i <= edges; ++i) {
        cin >> v1 >> v2 >> weight;
         
        // Adding Edge to the Directed Graph
        adjacencyList[v1].push_back(make_pair(v2, weight));
    }
    
    // Printing Adjacency List
    cout << endl << "The Adjacency List-" << endl;
    for (auto& value : adjacencyList) {
        string vertex = value.first;
        list< pair<string, int> > adjacentVertices = value.second;
        list< pair<string, int> >::iterator itr = adjacentVertices.begin();
        
        cout << "adjacencyList[" << vertex << "]";
         
        while (itr != adjacentVertices.end()) {
        	cout << " -> " << (*itr).first << " (" << (*itr).second << ")";
            ++itr;
        }
        
        cout << endl;
    }
	
    return 0;
}

Feel free to comment if you have any doubts..! Keep practicing..! Happy Coding..! 😀

Leave a Reply