Go Program: Breadth-First Search (BFS)

This Go program demonstrates the Breadth-First Search (BFS) algorithm in a graph. The BFS algorithm is used to traverse or search tree or graph data structures. It starts at a given node (often called the ‘root’ node) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Program Explanation

The program includes a Graph structure which represents the graph structure and contains methods to add edges and perform BFS traversal.

Key components of the program include:

• The Graph structure which uses a map to represent the adjacency list of each vertex.
• The addEdge method to add edges between vertices in the graph.
• The BFS method to perform the BFS traversal starting from a given vertex.
• The main function to create the graph, add edges, and initiate the BFS traversal.

package main

import (
    "container/list"
    "fmt"
)

// Graph structure to represent the graph
type Graph struct {
    vertices int
    adjList  map[int][]int
}

// NewGraph function to create a new graph
func NewGraph(vertices int) *Graph {
    return &Graph{
        vertices: vertices,
        adjList:  make(map[int][]int),
    }
}

// AddEdge method to add an edge to the graph
func (g *Graph) AddEdge(src, dest int) {
    g.adjList[src] = append(g.adjList[src], dest)
    g.adjList[dest] = append(g.adjList[dest], src) // For undirected graph
}

// BFS method to perform BFS traversal
func (g *Graph) BFS(startVertex int) {
    visited := make([]bool, g.vertices)
    queue := list.New()

    visited[startVertex] = true
    queue.PushBack(startVertex)

    for queue.Len() > 0 {
        element := queue.Front()
        currentVertex := element.Value.(int)
        fmt.Print(currentVertex, " ")
        queue.Remove(element)

        for _, neighbor := range g.adjList[currentVertex] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue.PushBack(neighbor)
            }
        }
    }
}

func main() {
    g := NewGraph(6)
    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 2)
    g.AddEdge(1, 3)
    g.AddEdge(2, 4)
    g.AddEdge(3, 4)
    g.AddEdge(3, 5)

    fmt.Println("Breadth First Traversal starting from vertex 0:")
    g.BFS(0)
}