Depth-First Search (DFS) is a fundamental graph traversal algorithm used to explore nodes and edges of a graph systematically. DFS is particularly useful for tasks such as pathfinding, topological sorting, and cycle detection in graphs. This article provides a comprehensive guide to implementing DFS traversal in Go, complete with detailed explanations and well-documented code.

Problem Statement

Given a graph represented by vertices and edges, perform a DFS traversal starting from a specified source vertex. The traversal should visit all reachable vertices in the graph in a depthward motion, exploring as far as possible along each branch before backtracking.

Program Structure

The Go program to perform DFS traversal is structured as follows:

• Graph Representation: The graph is represented using an adjacency list, where each vertex has a list of its adjacent vertices.
• DFS Implementation: The program implements DFS using a recursive approach, marking vertices as visited and exploring their neighbors.
• Main Function: Demonstrates the usage of the DFS implementation with an example graph.

Go Program

package main

import (
    "fmt"
)

// Graph represents a graph using an adjacency list
type Graph struct {
    vertices int
    adjList  [][]int
}

// NewGraph initializes a new graph with a given number of vertices
func NewGraph(vertices int) *Graph {
    adj := make([][]int, vertices)
    for i := range adj {
        adj[i] = []int{}
    }
    return &Graph{
        vertices: vertices,
        adjList:  adj,
    }
}

// AddEdge adds an edge to the graph
// For undirected graphs, edges are added in both directions
func (g *Graph) AddEdge(src, dest int, directed bool) {
    if src >= g.vertices || dest >= g.vertices || src < 0 || dest < 0 {
        fmt.Println("Invalid edge!")
        return
    }
    g.adjList[src] = append(g.adjList[src], dest)
    if !directed {
        g.adjList[dest] = append(g.adjList[dest], src)
    }
}

// DFS performs Depth-First Search traversal from a given source vertex
func (g *Graph) DFS(source int) []int {
    var traversalOrder []int
    visited := make([]bool, g.vertices)
    g.dfsUtil(source, visited, &traversalOrder)
    return traversalOrder
}

// dfsUtil is a helper function for DFS
func (g *Graph) dfsUtil(v int, visited []bool, traversalOrder *[]int) {
    // Mark the current vertex as visited and add it to the traversal order
    visited[v] = true
    *traversalOrder = append(*traversalOrder, v)

    // Recur for all the vertices adjacent to this vertex
    for _, neighbor := range g.adjList[v] {
        if !visited[neighbor] {
            g.dfsUtil(neighbor, visited, traversalOrder)
        }
    }
}

func main() {
    // Example usage:
    // Create a graph with 5 vertices (0 to 4)
    g := NewGraph(5)

    // Add edges to the graph (undirected)
    g.AddEdge(0, 1, false)
    g.AddEdge(0, 2, false)
    g.AddEdge(1, 3, false)
    g.AddEdge(1, 4, false)
    g.AddEdge(2, 3, false)
    g.AddEdge(3, 4, false)

    // Perform DFS traversal from vertex 0
    source := 0
    traversal := g.DFS(source)

    // Print the DFS traversal order
    fmt.Printf("DFS Traversal starting from vertex %d: %v\n", source, traversal)
}
    

Documentation

The Go program provided implements Depth-First Search (DFS) traversal for a graph. Below is a detailed explanation of each component of the program:

1. Graph Representation

The Graph struct represents the graph using an adjacency list. An adjacency list is an efficient way to represent sparse graphs, where each vertex has a list of its adjacent vertices.

Graph Struct

type Graph struct {
    vertices int
    adjList  [][]int
}
    

Fields:

• vertices: The number of vertices in the graph.
• adjList: A slice of slices where each sub-slice contains the adjacent vertices for a given vertex.

NewGraph Function

// NewGraph initializes a new graph with a given number of vertices
func NewGraph(vertices int) *Graph {
    adj := make([][]int, vertices)
    for i := range adj {
        adj[i] = []int{}
    }
    return &Graph{
        vertices: vertices,
        adjList:  adj,
    }
}
    

The NewGraph function initializes a new graph with a specified number of vertices. It creates an empty adjacency list for each vertex.

AddEdge Method

// AddEdge adds an edge to the graph
// For undirected graphs, edges are added in both directions
func (g *Graph) AddEdge(src, dest int, directed bool) {
    if src >= g.vertices || dest >= g.vertices || src < 0 || dest < 0 {
        fmt.Println("Invalid edge!")
        return
    }
    g.adjList[src] = append(g.adjList[src], dest)
    if !directed {
        g.adjList[dest] = append(g.adjList[dest], src)
    }
}
    

The AddEdge method adds an edge to the graph. If the graph is undirected, the edge is added in both directions to ensure bidirectional connectivity.

2. DFS Function

// DFS performs Depth-First Search traversal from a given source vertex
func (g *Graph) DFS(source int) []int {
    var traversalOrder []int
    visited := make([]bool, g.vertices)
    g.dfsUtil(source, visited, &traversalOrder)
    return traversalOrder
}

// dfsUtil is a helper function for DFS
func (g *Graph) dfsUtil(v int, visited []bool, traversalOrder *[]int) {
    // Mark the current vertex as visited and add it to the traversal order
    visited[v] = true
    *traversalOrder = append(*traversalOrder, v)

    // Recur for all the vertices adjacent to this vertex
    for _, neighbor := range g.adjList[v] {
        if !visited[neighbor] {
            g.dfsUtil(neighbor, visited, traversalOrder)
        }
    }
}
    

The DFS method performs the Depth-First Search traversal from a specified source vertex. It returns a slice of integers representing the order in which vertices are visited.

Steps:

1. Initialization:
   • traversalOrder: A slice to store the order of traversal.
   • visited: A boolean slice to keep track of visited vertices, initialized to false.
2. DFS Traversal:
   • The dfsUtil helper function is called recursively for each unvisited adjacent vertex.
   • Each vertex is marked as visited and added to the traversalOrder.
   • The function explores as far as possible along each branch before backtracking.
3. Completion: Once the traversal is complete, the traversalOrder slice contains the DFS traversal sequence.

3. Main Function

func main() {
    // Example usage:
    // Create a graph with 5 vertices (0 to 4)
    g := NewGraph(5)

    // Add edges to the graph (undirected)
    g.AddEdge(0, 1, false)
    g.AddEdge(0, 2, false)
    g.AddEdge(1, 3, false)
    g.AddEdge(1, 4, false)
    g.AddEdge(2, 3, false)
    g.AddEdge(3, 4, false)

    // Perform DFS traversal from vertex 0
    source := 0
    traversal := g.DFS(source)

    // Print the DFS traversal order
    fmt.Printf("DFS Traversal starting from vertex %d: %v\n", source, traversal)
}
    

The main function demonstrates how to use the DFS implementation:

1. Graph Creation: Initializes a graph with 5 vertices.
2. Adding Edges: Adds undirected edges between vertices to form the graph’s structure.
3. DFS Traversal: Performs DFS traversal starting from vertex 0.
4. Output: Prints the order in which vertices are visited during the DFS traversal.

How the Program Works

1. Graph Initialization: A new graph with 5 vertices is created using the NewGraph function.
2. Adding Edges: Undirected edges are added between vertices using the AddEdge method, establishing the graph’s connectivity.
3. DFS Traversal:
   • The DFS function is called with the source vertex (0).
   • The function marks the source vertex as visited and adds it to the traversal order.
   • It recursively visits each unvisited adjacent vertex, continuing this process until all reachable vertices are visited.
4. Output: The program prints the order in which vertices are visited during the DFS traversal.

Example Output

Given the following graph with vertices and edges:

• Vertex 0 connected to Vertex 1 and Vertex 2
• Vertex 1 connected to Vertex 3 and Vertex 4
• Vertex 2 connected to Vertex 3
• Vertex 3 connected to Vertex 4

Running the program produces the following output:

DFS Traversal starting from vertex 0: [0 1 3 4 2]
    

This output indicates that the DFS traversal starting from vertex 0 visits the vertices in the order: 0, 1, 3, 4, 2.

Conclusion

Depth-First Search (DFS) is a powerful graph traversal technique essential for various applications in computer science and engineering. The provided Go implementation offers a clear and efficient way to perform DFS traversal on both directed and undirected graphs. By understanding the program structure and the underlying DFS principles, developers can apply this algorithm to a wide range of problems, including pathfinding, topological sorting, and cycle detection.

Excerpt

Implement DFS traversal in Go with a comprehensive guide. This article includes detailed explanations and a well-documented Go program example.