JAVA - SCRIPT-ADJACENCY LIST CODE

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

Example :

<html>
<body>    
<script>  

    function insertVertex(vertex) {
        vertices.push(vertex)
    }	

    function constructAdjacencyList(adjcList, u, val) {
        adjcList.push([])
        adjcList[u].push(val)
    }	

    function printAdjacencyList(adjcList, vertices) {
        let i = 0
        for (vtx of vertices) {
            document.write("The Adjacency List for vertex ", vtx, " at index ", i, " : ", end = " ")
            for (let j = 0; j < adjcList[i].length; j++) {
                document.write(adjcList[i][j], end = " --> ")
            }	
            document.write("</br>")
            i++;
        }
    }			


    var vertices = []

    var adjacencyList = [[]]

    // Insert Vertices
    insertVertex("a")
    insertVertex("b")
    insertVertex("c")
    insertVertex("d")
    insertVertex("e")

    // Create Adjacency List

    constructAdjacencyList(adjacencyList, 0, "b")
    constructAdjacencyList(adjacencyList, 0, "c")
    constructAdjacencyList(adjacencyList, 0, "d")

    constructAdjacencyList(adjacencyList, 1, "a")
    constructAdjacencyList(adjacencyList, 1 ,"e")

    constructAdjacencyList(adjacencyList, 2, "a")
    constructAdjacencyList(adjacencyList, 2, "d")
    constructAdjacencyList(adjacencyList, 2, "e")

    constructAdjacencyList(adjacencyList, 3, "a")
    constructAdjacencyList(adjacencyList, 3 ,"c")
    constructAdjacencyList(adjacencyList, 3, "e")

    constructAdjacencyList(adjacencyList, 4, "b")
    constructAdjacencyList(adjacencyList, 4, "c")
    constructAdjacencyList(adjacencyList, 4, "d")

    printAdjacencyList(adjacencyList, vertices)

</script>
</body>
</html>

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 -->

Code explanation for Adjacency List Data Structure

There are two methods in the above code :

function insertVertex(vertex)

function constructAdjacencyList(adjcList, u, val)

While the first method is quite simple.

Explanation of function insertVertex(vertex) method :

function insertVertex(vertices, vertex) {
	vertices.push(vertex)
}

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

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

So, we have created a Linked List to hold the vertices.

var vertices = []

Then we call the function insertVertex(...) method and pass the vertex a to the method.

insertVertex("a")

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

vertices.push(vertex)

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

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

Explanation of function constructAdjacencyList(adjcList, u, val) method :

function constructAdjacencyList(adjcList, u, val) {
	adjcList.push([])
	adjcList[u].push(val)
}

Let's start from the beginning. Where we have defined a 2D Linked List to hold the Adjacency List.

adjacencyList = [[]]

But why do we need a 2D Linked 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 Linked 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 function constructAdjacencyList(...) method.

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 function constructAdjacencyList(...) method definition.

And we come across the first line :

adjcList.push([])

Now, since adjcList is a 2D Linked List, we need to initialise the first row(As mentioned in the diagram) with a Linked List (i.e. [])

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 Linked List.

adjcList[u].push(val)

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

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

Then, add b to the Lined List.

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

And the below Linked List is formed.

Then, we come to the next line in the main program.

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 function constructAdjacencyList(...) method definition.

And we come across the first line :

adjcList.push([])

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

adjcList[u].push(val)

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

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

Then, add c to the Lined List.

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

And the below Linked List is formed.

Similarly, we come to the next line in the main program.

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 Linked 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 function constructAdjacencyList(...) method.

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 function constructAdjacencyList(...) method definition.

And we come across the first line :

adjcList.push([])

Now, since adjcList is a 2D Linked List, we need to initialise the 2nd row(As mentioned in the diagram) with a Linked List (i.e. [])

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 Linked List.

adjcList[u].push(val)

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

adjcList[1] 		[Since the value of u is 1]

Then, add 1 to the Lined List.

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

And the below Linked List is formed.

And continuing this way we get the Adjacency List.

❮❮ PREV NEXT ❯❯