Depth First Search (DFS) Technique in Go

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
It uses a stack data structure, either explicitly or implicitly through recursion, to keep track of the vertices to be visited next.
DFS can be used to solve various problems such as finding connected components, topological sorting, and detecting cycles in graphs.

Go Implementation of DFS

// Package main provides the entry point to the program
package main

// Import necessary packages
import (
    "fmt"
)

/**
 * Graph structure represents a graph using an adjacency list representation.
 */
type Graph struct {
    V    int                 // Number of vertices
    adj  map[int][]int            // Adjacency list
}

/**
 * NewGraph initializes a new graph with the given number of vertices.
 * 
 * @param v Number of vertices
 * @return Graph
 */
func NewGraph(v int) *Graph {
    g := &Graph{
        V:   v,
        adj: make(map[int][]int),
    }
    return g
}

/**
 * AddEdge adds an edge from vertex v to vertex w.
 * 
 * @param v Source vertex
 * @param w Destination vertex
 */
func (g *Graph) AddEdge(v, w int) {
    g.adj[v] = append(g.adj[v], w)
}

/**
 * DFSUtil is a recursive function used by DFS.
 * 
 * @param v The starting vertex
 * @param visited Array to keep track of visited vertices
 */
func (g *Graph) DFSUtil(v int, visited []bool) {
    // Mark the current node as visited and print it
    visited[v] = true
    fmt.Print(v, " ")

    // Recur for all the vertices adjacent to this vertex
    for _, n := range g.adj[v] {
        if !visited[n] {
            g.DFSUtil(n, visited)
        }
    }
}

/**
 * DFS performs a Depth First Search traversal starting from vertex v.
 * 
 * @param v The starting vertex
 */
func (g *Graph) DFS(v int) {
    // Mark all the vertices as not visited (default is false in Go)
    visited := make([]bool, g.V)

    // Call the recursive helper function to print DFS traversal
    g.DFSUtil(v, visited)
}

/**
 * Main method to test the DFS algorithm.
 */
func main() {
    g := NewGraph(4)

    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 2)
    g.AddEdge(2, 0)
    g.AddEdge(2, 3)
    g.AddEdge(3, 3)

    fmt.Println("Following is Depth First Traversal (starting from vertex 2)")

    g.DFS(2)
}

Explanation

The above program demonstrates the Depth First Search (DFS) algorithm in Go:

  • Graph Structure: The Graph structure represents a graph using an adjacency list representation. It has methods to add edges and perform DFS.
  • DFSUtil Method: This is a recursive method used by the DFS method to visit nodes. It marks the current node as visited, prints it, and then recursively visits all adjacent vertices that have not been visited yet.
  • DFS Method: This method initializes the visited array and calls the DFSUtil method to start the traversal from the given starting vertex.
  • Main Method: This is the entry point of the program where a graph is created, edges are added, and the DFS traversal is initiated starting from vertex 2.

In the main method, we create a graph with 4 vertices and add edges between them. The DFS traversal starts from vertex 2 and prints the nodes in the order they are visited.

 

By Aditya Bhuyan

I work as a cloud specialist. In addition to being an architect and SRE specialist, I work as a cloud engineer and developer. I have assisted my clients in converting their antiquated programmes into contemporary microservices that operate on various cloud computing platforms such as AWS, GCP, Azure, or VMware Tanzu, as well as orchestration systems such as Docker Swarm or Kubernetes. For over twenty years, I have been employed in the IT sector as a Java developer, J2EE architect, scrum master, and instructor. I write about Cloud Native and Cloud often. Bangalore, India is where my family and I call home. I maintain my physical and mental fitness by doing a lot of yoga and meditation.

Leave a Reply

Your email address will not be published. Required fields are marked *

error

Enjoy this blog? Please spread the word :)