Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   
JAVA SPRING SPRINGBOOT HIBERNATE HADOOP HIVE ALGORITHMS PYTHON GO KOTLIN C# RUBY C++


❮❮ PREV NEXT ❯❯


GO - DFS - DEPTH FIRST SEARCH CODE - RECURSIVE



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

We will be seeing the Recursive way for implementing Depth First Search (DFS).


In the Recursive code we don't have to create the stack and maintain it as Go will do the job for us. And the stack will be hidden from us.


DFS - Depth First Search code for Undirected Graph - Recursive approach


Example : 



package main
import "fmt"
import "sort"


var vertices []string
var adjacencyList [][]string
var visited []bool

func insertVertex(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 depthFirstSearch(source string){

    sourceIndex := sort.StringSlice(vertices).Search(source)

    visited[sourceIndex] = true

    fmt.Print(source+"   ");

    for j := 0; j < len(adjacencyList[sourceIndex]); j++ {

        str := adjacencyList[sourceIndex][j]
		i := sort.StringSlice(vertices).Search(str)

        if (visited[i] == false) {

            visited[i] = true;
            depthFirstSearch(str)
        }
    }
}
	
func main() {
    
    const V = 6
    
    var tempList[]string
    
    visited = make([]bool, V)

    // Adding vertices one by one

    insertVertex("a")
    insertVertex("b")
    insertVertex("c")
    insertVertex("d")
    insertVertex("e")
    insertVertex("f")

    // Create Adjacency List

	constructTempList(&tempList, "c")
    constructTempList(&tempList, "d")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "d")
    constructTempList(&tempList, "e")
    constructTempList(&tempList, "c")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "a")
    constructTempList(&tempList, "b")
    constructTempList(&tempList, "e")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "a")
    constructTempList(&tempList, "b")
    constructTempList(&tempList, "e")
    constructTempList(&tempList, "f")
    
    constructAdjacencyList(&adjacencyList, &tempList)
        
    constructTempList(&tempList, "b")
    constructTempList(&tempList, "c")
    constructTempList(&tempList, "d")
    constructTempList(&tempList, "f")
    
    constructAdjacencyList(&adjacencyList, &tempList)
    
    constructTempList(&tempList, "d")
    constructTempList(&tempList, "e") 
    
    constructAdjacencyList(&adjacencyList, &tempList)   
    
    depthFirstSearch("a")
    
    fmt.Println()
    
}


Output :



  a c b d e f

We have implemented Depth First Search (DFS) on the below graph :

java_Collections

We can take various ways to navigate the graph using Depth First Search (DFS). Just remember our main intension is to visit all the vertices.


In this case we have covered the graph in the following path :


a --> c --> b --> d --> e --> f

Let us see how ?


Code Explanation for DFS - Depth First Search - Iterative :


Below code explains the methods :



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

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

  • func insertVertex(vertex string)

Almost the same we have discussed in BFS. You can skip it if you wane to.



Click Here - To understand the details of the methods 'func constructTempList(tmpList *[]string, val string)' and 'func insertVertex(vertex string)'.


Let's list out, what all do we need to support Depth First Search Data Structure.

  1. We need an Array to store the vertices.
    java_Collections

  2. We need a 2D Array to store the adjacency list.
    java_Collections

  3. We need a Queue and an array to store its Levels.

  4. We need a boolean array to store the Vertices that are already visited.

Now, let us see the above code.


We have an Array to store the Vertices.


var vertices []string

We also have a 2D Array to store the Adjacency List.


var adjacencyList [][]string

Similarly, we have a stack defined inside the method depthFirstSearch(...).


var stack[]string

And, there is a boolean array to store the Vertices that are visited.


var visited []bool

So, the first thing we will do is, insert the Vertices to the Array var vertices []string.


insertVertex("a")
insertVertex("b")
insertVertex("c")
insertVertex("d")
insertVertex("e")
insertVertex("f")

Explanation of 'func insertVertex(vertex string)' method 


func insertVertex(vertex string) {

	vertices = append(vertices, vertex)
}

func insertVertex(vertex string) is quite simple.


There is just one statement in it.


vertices = append(vertices, vertex)

It accepts vertex string as a parameter and adds it to the Array, vertices.

java_Collections

The next thing we will do is, create an Adjacency List to track the Adjacent Vertices.


Let us take the example of vertex a, to explain the creation of Adjacency List.


As we have seen, a has two adjacent vertices(i.e. c and d). And we have used the constructTempList(...) method to construct the Adjacency List.


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

And add the tempList[] Array with adjacent vertices to the Adjacency List Array var adjacencyList [][]string.


constructAdjacencyList(&adjacencyList, &tempList)

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


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

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

Initially, we create a tmpList[] Array. That would just hold the adjacent vertices of one node temporarily.


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


Then we take the tempList[] Array and pass it to the func constructAdjacencyList(...).


constructAdjacencyList(&adjacencyList, &tempList)

And in the first line itself,


*adjcList = append(*adjcList, *tmpList)

We are adding the contents of tempList[] array to the first row of adjcList[][] array.

java_Collections

So that the first row can hold the Adjacency List for vertex a.

java_Collections

Now, we come across the most important method func depthFirstSearch(source string) that performs the Depth First Search (DFS).


Explanation of 'func depthFirstSearch(source string)' method 


func depthFirstSearch(source string){

	sourceIndex := sort.StringSlice(vertices).Search(source)

	visited[sourceIndex] = true

	fmt.Print(source+"   ");

	for j := 0; j < len(adjacencyList[sourceIndex]); j++ {

		str := adjacencyList[sourceIndex][j]
		i := sort.StringSlice(vertices).Search(str)

		if (visited[i] == false) {

			visited[i] = true;
			depthFirstSearch(str)
		}
	}
}

We have called the func depthFirstSearch(source string) from the main method passing a as the parameter.


depthFirstSearch("a")

So, the first thing that we have done is, take the index of a,


sourceIndex := sort.StringSlice(vertices).Search(source)

Now, if we see the List of vertices,

java_Collections

We can see that a lies in index 0.


Next, we mark a as visited,


visited[sourceIndex] = true

in the visited[] array,


visited[0] = true
java_Collections


Then we print the vertex a.


fmt.Print(source+"   ")

Output :



 
  a

Then comes the for(...) loop, where we find the adjacent vertices of the top element(i.e. a).


for j := 0; j < len(adjacencyList[sourceIndex]); j++ {

	str := adjacencyList[sourceIndex][j]
	i := sort.StringSlice(vertices).Search(str)

	if (visited[i] == false) {

		visited[i] = true;
		depthFirstSearch(str)
	}
}

Now, in the first line of for loop, str contains the first adjacent vertex c.


str := adjacencyList[sourceIndex][j]

Next, we find the index of vertex c,


i := sort.StringSlice(vertices).Search(str)

Now, if we see the List of vertices,

java_Collections

We can see that c lies in index 2.


So, we check if c is visited or not.


if (visited[i] == false) {

	visited[i] = true
	depthFirstSearch(str)
}

Now, if we check the visited array,

java_Collections

We found that visited[2] = false and we get into the if statement.


And marked visited[2] = true,


visited[i] = true;

In the visited[] array,

java_Collections

And then comes the fun part. Where the depthFirstSearch(...) method calls itself.


depthFirstSearch(str)

So, internally what happens is, Go maintains an internal stack, that is hidden from you.


Now, since the method started from a, Go puts a to the stack. Then whenever it meets the statement,


depthFirstSearch(str)

It recognises a recursive call is made and pushes the content of variable str(i.e. c) to the stack.

java_Collections

Similarly, we repeat the same process until all the vertices are visited. And Go pushes all the values to the stack.

java_Collections
java_Collections

Now, since we have reached a place where all the adjacent vertices of vertex f are visited.


So, it's time for Go to backtrack. i.e. Start popping out all the elements from its internal queue.


So, it takes out f out of the queue and checks if there are any adjacent vertices of e that are not visited.

java_Collections

Continuing in the same way, all the elements are popped out of the Queue and the execution ends.





❮❮ PREV NEXT ❯❯