Graph Representation – Adjacency List in C++

This article discusses the Implementation of Graphs using Adjacency List in C++. There are two widely used methods of representing Graphs, these are:

Adjacency List
Adjacency Matrix

However, in this article, we will solely focus on the representation of graphs using the Adjacency List.

What are the Graphs?

A graph is a data structure that:

has a finite number of nodes or vertices
has a finite number of edges or arcs
is non-linear

Graphs are widely used to model real-life problems. For instance, in networking on social media, shortest-path finding problems, to name a few.

What is a non-linear data structure?

A non-linear data structure is one that has multiple levels associated with it. Unlike data structures like arrays, linked lists which have only a single level. Also, trees, heaps are some other examples of non-linear data structures.

Important Terminologies

Before we dive deep into Graph representations, here are some terminologies associated with Graphs you need to know.

Nodes
- These are vertices connected via links.
- Nodes are usually numbered from ‘0’.
Edges
- These are usually represented in the form (a, b), which represents a link between nodes ‘a’ and ‘b’. In case, of directed links, it represents a link from node ‘a’ to node ‘b’.
Undirected Graph
- Any collection of nodes, connected by a path that allows for movement in either direction.
- Here, the edges have no defined direction. Represented by a line segment connecting the nodes.
Directed Graph
- Any collection of nodes, connected by a path that allows for movement in a defined direction. That is, connected via a pointed-link.
- In this case, the edges are called arcs.
- In case, of connections in both directions, the two arcs may be replaced by bi-directional arrows.
Sparse Graph
- A graph having a relatively less number of links or edges, while compared with the number of maximum possible connections.
Dense Graph
- A graph having a large number of links or edges. Almost as many as the maximum possible number of connections.

Now, you are likely to have a basic understanding of Graphs and some terms associated with it. Therefore, we move onto the representation methods.

Graph Representation – Adjacency List

In this method, we add the index of the nodes ( or, say, the node number ) linked with a particular node in the form of a list. This is implemented using vectors, as it is a more cache-friendly approach. So, feel free to read about vectors here.

Have a look at the images displayed above. The image to the right is the adjacency-list implementation of the graph shown in the left.

As mentioned earlier, we may represent graphs using several methods. This method is widely employed to represent graphs. Let us first have a look at the advantages and disadvantages of using this method.

Advantages

Best suited for sparse graphs.
It takes relatively less space compared to an alternative implementation using a matrix. Worst-case space complexity is O( n²).
Adding nodes is easy and takes relatively less execution time.

Disadvantages

Not suited for dense graphs.
Accessing a particular link takes relatively more time. O( n ) when compared to O( 1 ) in the case of the Adjacency Matrix.

Where ‘n’ is the number of nodes.

C++ Code for Graph Representation – Adjacency List

#include<iostream>
#include<vector>

using namespace std;

void addNewEdge(vector<int> adjacencyList[], int a, int b)
{
  adjacencyList[a].push_back(b);
  adjacencyList[b].push_back(a);
}

void viewGraph(vector<int> adjacencyList[], int nodes)
{
  for (int i = 0; i < nodes; i++)
  {
    cout << "\nAdjacency List of node '"<< i <<"'";

    for (int j=0; j<adjacencyList[i].size() ; j++)
        {
            cout << " -> " << adjacencyList[i][j];
        }

    cout<<endl;
  }
}

int main()
{
  int nodes = 5;

  vector<int> adjacencyList[nodes];

  addNewEdge(adjacencyList, 0, 1);
  addNewEdge(adjacencyList, 0, 3);
  addNewEdge(adjacencyList, 1, 2);
  addNewEdge(adjacencyList, 1, 3);
  addNewEdge(adjacencyList, 2, 3);
  addNewEdge(adjacencyList, 3, 4);

  viewGraph(adjacencyList, nodes);

  return 0;
}

Output

Adjacency List of node '0' -> 1 -> 3

Adjacency List of node '1' -> 0 -> 2 -> 3

Adjacency List of node '2' -> 1 -> 3

Adjacency List of node '3' -> 0 -> 1 -> 2 -> 4

Adjacency List of node '4' -> 3

Analysis

In the above code, we initialize a vector and push elements into it using the push_back( value ) function. The nodes that are linked to a particular node are added into a list, again, a vector, corresponding to the index of the node under consideration. Finally, the graph is printed, looping through the vector, one by one. Now, if we were to add another node, this is much easier here while compared with the matrix implementation. In contrast, if we were asked to check if there is a link between two nodes, that would be difficult when compared with the matrix implementation – which takes just O( 1 ) time.

Also, if we look at the space consumed, it is less than and in the worst case equal to that by the other implementation. This is because we allocate memory only for nodes that are linked to a particular node. Rather than directly declaring a memory equivalent to that of a complete graph.

In the code below, these two statements insert links between ‘a’ and ‘b’ in both directions since in an undirected graph, there is a path from node ‘a’ to node ‘b’ and vice-versa.

void addNewEdge(vector<int> adjacencyList[], int a, int b)
{
  adjacencyList[a].push_back(b);
  adjacencyList[b].push_back(a);
}

However, if it is a directed graph, there is just one direction for the link between node ‘a’ and ‘b’ and in the order from node ‘a’ to node ‘b’. Therefore, the above block may be replaced by this.

void addNewEdge(vector<int> adjacencyList[], int a, int b)
{
  adjacencyList[a].push_back(b);
}

Once you are comfortable with the graph-related concepts, feel free to read the following graph-implementation problems in C++: