C++

Adjacency List in C++

In this post, we’ll use the adjacency list to describe how a graph is represented. Three techniques are frequently employed to illustrate the graph:

  1. Adjacency List
  2. Matrix of Adjacency
  3. An Incidence Matrix

This article’s primary topic will be the adjacency list.

Let’s first try to understand what a graph truly is before we get into it to understand this idea better.

Graph

A graph has a fixed number of nodes or vertices. And each node was connected by a line, which we called an edge. The edge is basically for communication between two vertices or nodes. For example, in the previous graph, we see six vertices or nodes ( 0, 1, 2, 3, 4, and 5). From vertex or node 0, we can easily move to vertex 1 and 3 because there is a direct connection between them. But there is no direct connection between vertex or node 0 and 4.

The graph is used in many real-life applications to solve network problems. For example, on Facebook, the user’s profile is a node or vertex, and the user’s friends in the list are further different nodes or vertices that have direct connections between them.

Types of Graphs

There are primarily two types of graphs:

1. Undirected Graph

The undirected graph is very famous because it is a bi-directional graph.

The adjacency list is a list of arrays where the size of the array is equal to the number of nodes present in the graph. And each node also has a sub-array that represents its connectivity to other nodes or vertices.

For example:
Below is an example of an undirected graph:


Undirected Graph

In the undirected graph, we can move to any vertex. For example, if there is a connection between nodes A and B, then we can also move from B to A.

2. Directed Graph

In a directed graph, the edges have direction edges. So these arrow edges will tell us how we can move in the graph from one vertex to another vertex, but only in some conditions. For example, if there is a directed edge between the nodes A and B, then we can quickly move from the vertex A to B but not back from B to A if there is no directed edge from B to A.


Directed Graph

We are going to discuss the adjacency lists of both types of graphs (undirected and directed).

Undirected Graph Adjacency List

Adjacency List

In the previous undirected graph, we can see six vertices (0, 1, 2, 3, 4, 5). So, we have an array of six vertices. And each further individual vertex has its own linked list or adjacency list, as shown in the previous adjacency list. We can see that vertex 0 points to vertex 4 and vertex 3.

But, as we have explained before, an undirected graph can move in both directions. There is an edge between nodes 0 and 4 and a direct connection between 0 to 4. But due to the undirected graph, there is also a connection between 4 to 0. That’s why if you look into the previous adjacency list, the vertex 4 also points to the vertex 0. The same is also true in the case of vertex 3. The adjacency list of vertex 3 also points to the vertex 0.

Directed Graph Adjacency List

The above image is a directed graph, and on the right side is its adjacency list. In this adjacency list, we can see a direct edge from node 1 to node 2 but not from node 2 to 1. So, we can only move in one direction, that is, from 1 to 2. The same is also in the adjacency list. We can see no link from vertex 2 to 1 in the adjacency list of 2.

Adjacency Matrix

The matrix is used in this method to represent the details of the graph vertices. The size of the matrix depends upon the number of vertices in the graph. For example, if any graph has 5 vertices, then the size of the matrix will be 5 x 5. In this, the row and column are the vertices themselves. The matrix representation of the adjacency list uses either 1 or 0 to fill the matrix. The value of 1 represents a path from row vertex to column vertex, but the value of 0 represents no path between row vertex and column vertex.

Undirected Graph Matrix Adjacency List

In the above matrix adjacency list, we can see that A to E is value 0 because there is no path between them. So, we filled that value with 0. But there is a path from vertex B through A, and we filled that value with 1.

Directed Graph Matrix Adjacency List

In the above-directed matrix adjacency list, we can see that A to D is value 0 because there is no path from A to D, but a path exists from D to A, so we filled that value with 1.

Incidence Matrix

The matrix is used in this method to represent the details of the graph vertices. The size of the matrix depends upon the number of vertices and total edges in the graph. For example, if any graph has 5 vertices and 7 edges, then the size of the matrix will be 5 x 7. The edges will represent the columns, and the vertices will be on the row side. The matrix representation of the adjacency list uses either 0, 1, or -1 to fill the matrix values.

The value of 1 represents an outgoing path from row vertex to column vertex, but the value of 0 represents no path between row vertex and column vertex. The value of -1 represents an incoming path to the edge of the column vertex.

C++ Code for the Directed Graph Adjacency List

Directed graph

Adjacency list of directed graph

#include <iostream>
using namespace std;

// Syntax to create node
struct Node
{
    int value;
    Node* next;
};

// This will store the graph edge details (source and destination)
struct graphEdge {
    int source, destination;
};

class GraphAdjacencyList
{
    // Create a new node for the adjacency list
    Node* getNeighbourVertex(int destination, Node* head_node)
    {
        Node* new_node = new Node;
        new_node->value = destination;

        new_node->next = head_node;

        return new_node;
    }

    // It will store the total number of nodes in a graph
    int number_of_nodes;

public:
    Node **head_node;

    GraphAdjacencyList(graphEdge graphEdges[], int num, int number_of_nodes)
    {
        // dynamic memory allocation
        head_node = new Node*[number_of_nodes]();
        this->number_of_nodes = number_of_nodes;

        // initialize headnode for every edge of graph
        for (int k = 0; k < number_of_nodes; k++) {
            head_node[k] = nullptr;
        }

        for (int k = 0; k < num; k++)
        {
            int source = graphEdges[k].source;
            int destination = graphEdges[k].destination;

            Node* new_node = getNeighbourVertex(destination, head_node[source]);
            head_node[source] = new_node;


        }
    }

    ~GraphAdjacencyList() {
        for (int k = 0; k < number_of_nodes; k++) {
            delete[] head_node[k];
        }

        delete[] head_node;
    }
};

void display(Node* displayptr)
{
    while (displayptr != nullptr)
    {
        cout << " adjacency list —> " << displayptr->value;
        displayptr = displayptr->next;
    }
    cout << endl;
}

int main()
{

    graphEdge graphEdges[] =
    {
      // these are x and y values which represent an edge from x to y
        {0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 1}, {3, 4}
    };

    // total number of nodes from 0 to 5, so total nodes is 6
    int number_of_nodes = 6;

    // this method will calculate the number of edges in the graph
    int num_edges = sizeof(graphEdges)/sizeof(graphEdges[0]);

    // create the graph
    GraphAdjacencyList graph(graphEdges, num_edges, number_of_nodes);

      // display the adjacency list of the graph
    for (int k = 0; k < number_of_nodes; k++)
    {
        cout << k;

        display(graph.head_node[k]);
    }

    return 0;
}

Output:

0 adjacency list —> 1
1 adjacency list —> 2
2 adjacency list —> 1 adjacency list —> 0
3 adjacency list —> 4 adjacency list —> 2
4 adjacency list —> 1

C++ Code for the Directed Graph Adjacency List With Weight

Directed graph with weighted edges

Adjacency list of directed graph

#include <iostream>
using namespace std;

// Syntax to create node
struct Node
{
    int value,cost;
    Node* next;
};

// This will store the graph edge details (source and destination)
struct graphEdge {
    int source, destination,edgeweight;
};


class GraphAdjacencyList
{
    // Create a new node for the adjacency list
    Node* getNeighbourVertex(int destination,int edgeweight,
      Node* head_node)
    {
        Node* new_node = new Node;
        new_node->value = destination;
        new_node->cost = edgeweight;

        new_node->next = head_node;

        return new_node;
    }

    // It will store the total number of nodes in a graph
    int number_of_nodes;

public:
    Node **head_node;

    GraphAdjacencyList(graphEdge graphEdges[], int num, int number_of_nodes)
    {
        // dynamic memory allocation
        head_node = new Node*[number_of_nodes]();
        this->number_of_nodes = number_of_nodes;

        // initialize headnode for every edge of graph
        for (int k = 0; k < number_of_nodes; k++) {
            head_node[k] = nullptr;
        }

        for (int k = 0; k < num; k++)
        {
            int source = graphEdges[k].source;
            int destination = graphEdges[k].destination;
            int edgeweight = graphEdges[k].edgeweight;

            Node* new_node = getNeighbourVertex(destination, edgeweight,
                  head_node[source]);
            head_node[source] = new_node;


        }
    }


    GraphAdjacencyList() {
        for (int k = 0; k < number_of_nodes; k++) {
            delete[] head_node[k];
        }

        delete[] head_node;
    }

};


void display(Node* displayptr, int k)
{
    while (displayptr != nullptr)
    {
      cout << "(" << k << ", " <<
      displayptr->value << ", " << displayptr->cost << ") ";
        displayptr = displayptr->next;
    }
    cout << endl;
}


int main()
{

    graphEdge graphEdges[] =
    {
      // (x,y,z)=> these are x and y values which represent an edge    
      // from x to y with weight w
        {0, 1, 4}, {1, 2, 6}, {2, 0, 3}, {2, 1, 5}, {3, 4, 8},
        {4, 1, 1}, {3, 2, 7}
    };

    // total number of nodes from 0 to 5, so total nodes is 6
    int number_of_nodes = 6;

    // this method will calculate the number of edges in the graph
    int num_edges = sizeof(graphEdges)/sizeof(graphEdges[0]);

    // create the graph
    GraphAdjacencyList graph(graphEdges, num_edges, number_of_nodes);

      // display the adjacency list of the graph
    for (int k = 0; k < number_of_nodes; k++)
    {
        cout << k;

        display(graph.head_node[k],k);
    }

    return 0;
}

Output:

0(0, 1, 4)
1(1, 2, 6)
2(2, 1, 5) (2, 0, 3)
3(3, 2, 7) (3, 4, 8)
4(4, 1, 1)

Conclusion

In this article, we have seen different methods to represent the graph. We have also seen the incidence matrix, which is also a method to represent the graph matrix. Next, we discussed other C++ programming methods to represent the adjacency list (directed and weighted directed graphs). We have also studied directed and undirected graphs. We also came to know that a undirected graph is easy to handle as compared to a directed graph because an undirected graph is a bi-directional graph. After all, it’s not edge direction dependent like the directed graph.

About the author

Shekhar Pandey