GO - ADJACENCY LIST CODE

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

Example :

package main
import "fmt"

func insertVertex(vertices *[]string, vertex string) {

    *vertices = append(*vertices, vertex)
}

func constructTempList(tmpList *[]string, val string) {

	*tmpList = append(*tmpList, val)
}

func constructAdjacencyList(adjcList *[][]string, tmpList *[]string) {

    *adjcList = append(*adjcList, *tmpList)
    *tmpList = nil
}


func printAdjacencyList(adjcList *[][]string, vertices []string) {

    for i, edge := range *adjcList {
        	
        fmt.Print("Adjacency List for Vertex '",vertices[i],"' is")
        for _, edge1 := range edge {

            fmt.Print(" --> ",edge1)
        }	
    fmt.Println()    
    }    
}
	
func main() {

    var vertices[]string
    
    var tempList[]string

    var adjacencyList[][]string

    // Adding vertices one by one

    insertVertex(&vertices, "a")
    insertVertex(&vertices, "b")
    insertVertex(&vertices, "c")
    insertVertex(&vertices, "d")
    insertVertex(&vertices, "e")

    // Create Adjacency List

	constructTempList(&tempList, "b")
    constructTempList(&tempList, "c")
    constructTempList(&tempList, "d")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "a")
    constructTempList(&tempList, "e")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "a")
    constructTempList(&tempList, "d")
    constructTempList(&tempList, "e")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "a")
    constructTempList(&tempList, "c")
    constructTempList(&tempList, "e")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "b")
    constructTempList(&tempList, "c")
    constructTempList(&tempList, "d")
    
    constructAdjacencyList(&adjacencyList, &tempList)


    printAdjacencyList(&adjacencyList, vertices)
    
}

Output :

Adjacency List for Vertex 'a' is --> b --> c --> d
Adjacency List for Vertex 'b' is --> a --> e
Adjacency List for Vertex 'c' is --> a --> d --> e
Adjacency List for Vertex 'd' is --> a --> c --> e
Adjacency List for Vertex 'e' is --> b --> c --> d

Code explanation for Adjacency List Data Structure

There are three methods in the above code :

func insertVertex(vertices *[]string, vertex string)

func constructTempList(tmpList *[]string, val string)

func constructAdjacencyList(adjcList *[][]string, tmpList *[]string)

While the first method is quite simple.

Explanation of 'func insertVertex(vertices *[]string, vertex string)' method :

func insertVertex(vertices *[]string, vertex string) {
	*vertices = append(*vertices, vertex)
}

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

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

So, in the main(...) method, we have created an Array to hold the vertices.

var vertices[]string

Then we call the func insertVertex(vertices *[]string, vertex string) method and pass the Array vertices and the vertex a to the method.

insertVertex(vertices, "a")

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

*vertices = append(*vertices, vertex)

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

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

For adding the elements to the Adjacency List Array, we have two methods,

func constructTempList(tmpList *[]string, val string)

func constructAdjacencyList(adjcList *[][]string, tmpList *[]string)

The first method constructs a temporary array where the adjacency list of one node would be stored.

Say for example, the Adjacency List for Vertex a is b, c and d. And that's exactly we are storing in the temporary array.

var tempList[]string

Explanation of 'func constructTempList(tmpList *[]string, val string)' method :

func constructTempList(tmpList *[]string, val string) {

	*tmpList = append(*tmpList, val)
}

Let's start with at the main(...) method. Where we have defined the var tempList[]string Array.

var tempList[]string

Then we have passed the nodes, b, c and d, to the constructTempList(...)

constructTempList(&tempList, "b")
constructTempList(&tempList, "c")
constructTempList(&tempList, "d")

So that the nodes, b, c and d gets added to the tempList array.

Now, that we are able to add the Adjacent vertices to the tempList[] array.

And, it is time to call the func constructAdjacencyList(adjcList *[][]string, tmpList *[]string) and add the Adjacent vertices of vertex a(i.e. b, c and d) to the first row of the 2D Array adjcList[][].

	constructAdjacencyList(&adjacencyList, &tempList)

Explanation of 'func constructAdjacencyList(adjcList [][]string, tmpList []string) ' method :

func constructAdjacencyList(adjcList *[][]string, tmpList *[]string) {
	*adjcList = append(*adjcList, *tmpList)
	*tmpList = nil
}

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

var adjacencyList[][]string

But why do we need a 2D Array ?

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

But How ?

Let us consider vertex 'a' at index '0'

Let us take the tempList[] that currently holds the adjacent vertices of vertex a and pass it to func constructAdjacencyList(adjcList *[][]string, tmpList *[]string) method.

constructAdjacencyList(&adjacencyList, &tempList)

Now let's go to the func constructAdjacencyList(adjcList *[][]string, tmpList *[]string) method definition.

And we come across the first line :

*adjcList = append(*adjcList, *tmpList)

Where we are appending the tmpList[] array to the first row of the 2D Array, adjcList[][],

And the first row of adjcList[][] array is appended.

Then we reset the tempList[] Array, so that it can hold the fresh adjacency list for the next row.

*tmpList = nil

Then we follow the same process, i.e. Add the adjacent vertices of vertex b, i.e. a and d to the tmpList Array.

constructTempList(&tempList, "a")
constructTempList(&tempList, "e")

And once again, call the func constructAdjacencyList(adjcList *[][]string, tmpList *[]string) method.

And continuing this way we get the Adjacency List.

❮❮ PREV NEXT ❯❯