Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Graph Implementation

Understand how to implement graph data structures in C++ by using adjacency lists with linked lists. Learn to create directed and undirected graphs, add edges, and print the graph to visualize connections. This lesson equips you with foundational skills to manage graph representations and traversals in coding interviews.

We'll cover the following...

Introduction

At this point, we’ve understood the theoretical logic behind graphs. In this lesson, we will use the knowledge we have to implement the graph data structure in C++. Our graph will have directed edges.

The implementation will be based on the adjacency list model. The linked list class we created earlier will be used to represent adjacent vertices.

As a refresher, here is the illustration of the graph we’ll be producing using an adjacency list:

The Graph Class

Graph class consists of two data members:

  • The total number of vertices in the graph
  • A list of linked lists to store adjacent vertices

So let’s get down to the implementation!

C++
class Graph {
private:
//Total number of vertices
    int vertices;
//definining an array which can hold multiple LinkedLists equal to the number of vertices in the graph
    LinkedList * array;
public:
  
    Graph(int vertices) {
//Creating a new LinkedList for each vertex/index of the array
        array=new LinkedList[vertices];
    }
};
int main() {
    Graph myGraph(5);
    return 0;
}

We’ve laid down the foundation of our Graph class. The variable vertices contains an integer specifying the total number of vertices.

The second component is array, which will act as our adjacency list. We simply have to run a loop and create a linked list for each vertex.

Additional Functionality

Now, we’ll add two methods to make this class functional:

  1. printGraph() - Prints the contents of the graph
  2. addEdge() - Connects a source with a destination
C++
class Graph {
private:
    int vertices;
    LinkedList * array;
public:
    Graph(int v) {
        array=new LinkedList[v];
        vertices=v;
    }
    void addEdge(int source, int destination) {
         if (source < vertices && destination < vertices)
        array[source].insertAtHead(destination);
    }
    void printGraph() {
        cout << "Adjacency List of Directed Graph" <<endl;
        Node*temp;
        for(int i=0; i<vertices; i++) {
            cout << "|" << i << "| => ";
            temp = (array[i]).getHead();
            while(temp != NULL) {
                cout <<  "[" <<temp->data << "] -> ";
                temp = temp->nextElement;
            }
            cout <<"NULL"<<endl;
        }
    }
};
int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    cout << endl;
    g.printGraph();
    return 0;
}

Let’s break down the two new functions that we’ve implemented.

addEdge (source, destination)

Thanks to the graph constructor, source and destination are already stored as indices of our array. This function simply inserts a destination vertex into the adjacency linked list of the source vertex by running the following line of code:

array[source].insertAtHead(destination)

One important thing to note is that we are implementing a directed graph, so addEdge(0, 1) is not equal to addEdge(1, 0).

printGraph()

This function uses a simple nested loop to iterate through the adjacency list. Each linked list is being traversed here.

Undirected graph

So far, we have covered the implementation of a directed graph.

In the case of an undirected graph, we will have to create an edge from the source to the destination and from the destination to the source, making it a bidirectional edge:

array[source].insertAtHead(destination) 
array[destination].insertAtHead(source)

The complete implementation of an undirected graph class is shown below:

C++
#include "Graph.h"
using namespace std;
int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    cout << endl;
    g.printGraph();
    return 0;
}