Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to explore nodes and edges of a graph systematically. BFS is particularly useful for finding the shortest path in unweighted graphs, scheduling tasks, and solving puzzles. This article provides a comprehensive guide to implementing BFS traversal in Go, complete with detailed explanations and well-documented code.
Problem Statement
Given a graph represented by vertices and edges, perform a BFS traversal starting from a specified source vertex. The traversal should visit all reachable vertices in the graph in the order of their distance from the source vertex.
Program Structure
The Go program to perform BFS 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.
- Queue Implementation: BFS uses a queue to keep track of the vertices to be explored next.
- BFS Function: The BFS function performs the traversal, marking vertices as visited and enqueuing their adjacent vertices.
- Main Function: Demonstrates the usage of the BFS 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) } } // BFS performs Breadth-First Search traversal from a given source vertex func (g *Graph) BFS(source int) []int { // Initialize a slice to store the order of traversal var traversalOrder []int // Create a visited slice to keep track of visited vertices visited := make([]bool, g.vertices) visited[source] = true // Initialize a queue and enqueue the source vertex queue := []int{source} for len(queue) > 0 {
// Dequeue the first vertex from the queue
current := queue[0]
queue = queue[1:]
// Append the current vertex to the traversal order
traversalOrder = append(traversalOrder, current)
// Iterate through all adjacent vertices
for _, neighbor := range g.adjList[current] {
if !visited[neighbor] {
// Mark the neighbor as visited and enqueue it
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
return traversalOrder
}
func main() {
// Example usage:
// Create a graph with 6 vertices (0 to 5)
g := NewGraph(6)
// Add edges to the graph (undirected)
g.AddEdge(0, 1, false)
g.AddEdge(0, 2, false)
g.AddEdge(1, 3, false)
g.AddEdge(2, 4, false)
g.AddEdge(3, 4, false)
g.AddEdge(3, 5, false)
// Perform BFS traversal from vertex 0
source := 0
traversal := g.BFS(source)
// Print the BFS traversal order
fmt.Printf("BFS Traversal starting from vertex %d: %v\n", source, traversal)
}
Documentation
The Go program provided implements Breadth-First Search (BFS) 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. BFS Function
// BFS performs Breadth-First Search traversal from a given source vertex
func (g *Graph) BFS(source int) []int {
// Initialize a slice to store the order of traversal
var traversalOrder []int
// Create a visited slice to keep track of visited vertices
visited := make([]bool, g.vertices)
visited[source] = true
// Initialize a queue and enqueue the source vertex
queue := []int{source}
for len(queue) > 0 {
// Dequeue the first vertex from the queue
current := queue[0]
queue = queue[1:]
// Append the current vertex to the traversal order
traversalOrder = append(traversalOrder, current)
// Iterate through all adjacent vertices
for _, neighbor := range g.adjList[current] {
if !visited[neighbor] {
// Mark the neighbor as visited and enqueue it
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
return traversalOrder
}
The BFS method performs the Breadth-First Search traversal from a specified source vertex. It returns a slice of integers representing the order in which vertices are visited.
Steps:
- Initialization:
traversalOrder: A slice to store the order of traversal.visited: A boolean slice to keep track of visited vertices, initialized tofalse.queue: A slice used as a queue to manage the order of vertex exploration, initialized with the source vertex.
- Traversal:
- While the queue is not empty, dequeue the first vertex.
- Mark the vertex as visited and append it to the
traversalOrder. - Iterate through all adjacent vertices. If a neighbor hasn’t been visited, mark it as visited and enqueue it.
- Completion: Once the queue is empty, return the
traversalOrderslice containing the BFS traversal sequence.
3. Main Function
func main() {
// Example usage:
// Create a graph with 6 vertices (0 to 5)
g := NewGraph(6)
// Add edges to the graph (undirected)
g.AddEdge(0, 1, false)
g.AddEdge(0, 2, false)
g.AddEdge(1, 3, false)
g.AddEdge(2, 4, false)
g.AddEdge(3, 4, false)
g.AddEdge(3, 5, false)
// Perform BFS traversal from vertex 0
source := 0
traversal := g.BFS(source)
// Print the BFS traversal order
fmt.Printf("BFS Traversal starting from vertex %d: %v\n", source, traversal)
}
The main function demonstrates how to use the BFS implementation:
- Create a graph with 6 vertices.
- Add undirected edges between the vertices.
- Perform BFS traversal starting from vertex 0.
- Print the order in which vertices are visited.
How the Program Works
- Graph Initialization: A new graph with 6 vertices is created using the
NewGraphfunction. - Adding Edges: Undirected edges are added between vertices to form the graph’s structure.
- BFS Traversal:
- The BFS function starts by marking the source vertex as visited and enqueuing it.
- It enters a loop where it dequeues the first vertex, appends it to the traversal order, and enqueues all its unvisited neighbors after marking them as visited.
- This process continues until the queue is empty, ensuring that all reachable vertices are visited in the order of their distance from the source.
- Output: The program prints the BFS traversal order, showing the sequence in which vertices are visited.
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
- Vertex 2 connected to Vertex 4
- Vertex 3 connected to Vertex 4 and Vertex 5
Running the program produces the following output:
BFS Traversal starting from vertex 0: [0 1 2 3 4 5]
This output indicates that the BFS traversal starting from vertex 0 visits the vertices in the order: 0, 1, 2, 3, 4, 5.
Conclusion
Breadth-First Search (BFS) is a powerful and versatile graph traversal algorithm essential for solving various computational problems. The provided Go implementation offers a clear and efficient way to perform BFS traversal on both directed and undirected graphs. By understanding the program structure and the underlying BFS principles, developers can apply this algorithm to a wide range of applications, including network routing, social network analysis, and more.
Excerpt
Implement BFS traversal in Go with a comprehensive guide. This article includes detailed explanations and a well-documented Go program example.
