C - PLUS-PLUS-ADJACENCY LIST CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Example :

#include <iostream>
#include <vector>

using namespace std;

class AdjacencyListGraph {

	public:
	
    void insertVertex(vector<string> &vertices, string vertex) {

        vertices.push_back(vertex);
    }

    void constructAdjacencyList(vector<vector<string>> &adjcList, int u, string val) {

        adjcList.push_back(vector<string>());
        adjcList[u].push_back(val);
    }


    void printAdjacencyList(vector<vector<string>> &adjcList, vector<string> vertices) {

        int i = 0;
        for (string vtx : vertices) {

            cout <<  "The Adjacency List for vertex " << vtx << " at index " << i << " :" << endl;

            for (int j = 0; j < adjcList[i].size() ; j++) {

                cout << adjcList[i][j] << " --> ";
            }
            cout << endl;
            i++;
        }
    }
};


int main() {

    AdjacencyListGraph adjacencyListGraph;

    vector<string> vertices;

    vector<vector<string>> adjacencyList;

    // Insert Vertices

    adjacencyListGraph.insertVertex(vertices, "a");
    adjacencyListGraph.insertVertex(vertices, "b");
    adjacencyListGraph.insertVertex(vertices, "c");
    adjacencyListGraph.insertVertex(vertices, "d");
    adjacencyListGraph.insertVertex(vertices, "e");

    // Create Adjacency List

    adjacencyListGraph.constructAdjacencyList(adjacencyList, 0, "b");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 0, "c");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 0, "d");
        
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 1, "a");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 1 ,"e");
        
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 2, "a");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 2, "d");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 2, "e");
        
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 3, "a");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 3 ,"c");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 3, "e");
        
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 4, "b");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 4, "c");
    adjacencyListGraph.constructAdjacencyList(adjacencyList, 4, "d");

    adjacencyListGraph.printAdjacencyList(adjacencyList, vertices);
}

Output :

The Adjacency List for vertex a at index 0 :
b --> c --> d -->
The Adjacency List for vertex b at index 1 :
a --> e -->
The Adjacency List for vertex c at index 2 :
a --> d --> e -->
The Adjacency List for vertex d at index 3 :
a --> c --> e -->
The Adjacency List for vertex e at index 4 :
b --> c --> d -->

Note : In order to use ElementAt() method you must include 'using System.Linq;'.

Code explanation for Adjacency List Data Structure

There are two methods in the above code :

void insertVertex(vector<string> &vertices, string vertex)

void constructAdjacencyList(vector<vector<string>> &adjcList, int u, string val)

While the first method is quite simple.

Explanation of void insertVertex(vector<string> &vertices, string vertex) method :

void insertVertex(vector<string> &vertices, string vertex) {
	vertices.push_back(vertex);
}

As the name of the method void insertVertex(...) suggests. The method is used to add vertices to the List.

Let us take the example to add the vertex a to the List.

So, in the main(...) method, we have created a List to hold the vertices.

vector<string> vertices;

Then we call the void insertVertex(...) method and pass the List vertices and the vertex a to the method.

adjacencyListGraph.insertVertex(vertices, "a");

Now, if we go to the definition of the void insertVertex(...) method. We can see, there is just one line in it,

vertices.push_back(vertex);

That takes the vertex (a in this case) and adds it to the vertices List.

Next, let us come to the next method that creates the Adjacency List.

Explanation of void constructAdjacencyList(list &adjcList, int u, string val) method :

void constructAdjacencyList(vector<vector<string>> &adjcList, int u, string val) {

	adjcList.push_back(vector<string>());
	adjcList[u].push_back(val);
}

Let's start with at the main(...) method. Where we have defined a 2D List to hold the Adjacency List.

vector<vector<string>> adjacencyList;

But why do we need a 2D List?

Let us look at the below diagram to get it clarified.

Vertex a is at index 0. Similarly, vertex b is at index 1 and so on.

Now, we can consider the above as a 2D List.

But How?

Let us consider vertex a at index 0

Let us take vertex a at index 0. Then take its Adjacent Vertices and pass it to void constructAdjacencyList(...) method.

adjacencyListGraph.constructAdjacencyList(adjacencyList, 0, "b");

The first adjacent vertex of a at index 0 is b. So, we pass the index i.e. 0 and its adjacent vertex i.e. b.

Now let's go to the void constructAdjacencyList(...) method definition.

And we come across the first line :

adjcList.push_back(vector<string>());

Now, since adjcList is a 2D List, we need to initialise the first row(As mentioned in the diagram) with a Vector/List (i.e. vector<string>())

And this row will hold the Adjacent vertices of vertex a at index 0 (i.e. b, c & d)

And then comes the line that will be adding elements to the above created Vector/List.

adjcList[u].push_back(val);

So, in the above line, the first thing we do is, get the List at index 0

adjcList[0] 		[Since the value of 'u' is '0']

Then, add b to the Lined List.

adjcList[0].push_back("b"); 	[Since, the value of 'val' is 'b'].

And the below List is formed.

Then, we come to the next line in the main(...) method.

adjacencyListGraph.constructAdjacencyList(adjacencyList, 0, "c");

The second adjacent vertex of a at index 0 is c. So, we pass the index i.e. 0 and its adjacent vertex i.e. c.

Now let's come to the void constructAdjacencyList(...) method definition.

And we come across the first line :

adjcList.push_back(vector<string>());

And then comes the line that will be adding elements to the above created Vector/List.

adjcList[u].push_back(val);

So, in the above line, the first thing we do is, get the List at index 0

adjcList[0]		[Since the value of 'u' is '0']

Then, add c to the Lined List.

adjcList[0].push_back("c"); 	[Since, the value of 'val' is 'c'].

And the below List is formed.

Similarly, we come to the next line in the main(...) method.

adjacencyListGraph.constructAdjacencyList(adjacencyList, 0, "d");

The second adjacent vertex of a at index 0 is d. So, we pass the index i.e. 0 and its adjacent vertex i.e. d.

And the below List is formed.

Next, let us consider vertex b at index 1

Now, us take vertex b at index 1. Then take its Adjacent Vertices and pass it to void constructAdjacencyList(...) method.

adjacencyListGraph.constructAdjacencyList(adjacencyList, 1, "a");

The first adjacent vertex of b at index 1 is a. So, we pass the index i.e. 1 and its adjacent vertex i.e. a.

Now let's go to the void constructAdjacencyList(...) method definition.

And we come across the first line :

adjcList.push_back(vector<string>());

Now, since adjcList is a 2D List, we need to initialise the 2nd row(As mentioned in the diagram) with a List (vector<string>())

And this row will hold the Adjacent vertices of vertex b at index 1 (i.e. a & e).

And then comes the line that will be adding elements to the above created List.

adjcList[u].push_back(val);

So, in the above line, the first thing we do is, get the List at index 1

adjcList.ElementAt(1) 		[Since the value of 'u' is '1']

Then, add 1 to the Lined List.

adjcList[1].push_back("a"); 	[Since, the value of 'val' is 'a'].

And the below List is formed.

And continuing this way we get the Adjacency List.

❮❮ PREV NEXT ❯❯