Graph Algorithms Implementation in Go

Welcome to our session on Graph Algorithms Implementation. A large proportion of real-world problems, from social networking to routing applications, can be represented by graphs. Understanding and implementing graph algorithms is thus a key skill to have in your programming toolkit. In this lesson, we introduce and explore one of the most fundamental graph traversal algorithms — the Breadth-First Search (BFS).

A graph consists of nodes connected by edges. An adjacency list is a way of representing a graph as a collection of lists. In an adjacency list, each vertex u in the graph has a list that contains all of the vertices v that are adjacent to u. Here's a breakdown of how it works:

• Vertices: Each vertex in the graph has a corresponding list.
• Edges: If there is an edge between vertices u and v, then vertex v will appear in the list for vertex u, and vice versa for an undirected graph.

For example:

0 -> {1, 2}
1 -> {0}
2 -> {0, 3}
3 -> {2}

corresponds to this graph:

   0
  / \ 
 1   2 - 3

The Graph structure we will use is:

package main

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

func NewGraph() *Graph {
    return &Graph{adjList: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
    g.adjList[u] = append(g.adjList[u], v)
    g.adjList[v] = append(g.adjList[v], u) // Assuming an undirected graph
}

func (g *Graph) GetAdjList() map[int][]int {
    return g.adjList
}

In Go, you can use map[int][]int to represent the adjacency list, where each key represents a vertex, and the value is a slice of integers representing adjacent vertices. This setup is efficient for lookups and insertions.

Let's take a sneak peek at the BFS algorithm. Given a graph and a starting vertex, BFS systematically explores the edges of the graph, visiting all neighbors of a vertex before moving on to the next level. It does this by managing a queue of vertices yet to be explored and consistently visiting all vertices adjacent to the current one before moving on.

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It means that the first element added to the queue will be the first one to be removed.

For this graph:

       0
      / \
     1   2
    / \   \
   3   4   5

Running BFS starting at node 0 will visit: 0 -> 1 -> 2 -> 3 -> 4 -> 5

The algorithm for BFS is:

1. Initialization:

   • Start with an initial node (start).
   • Mark start as visited.
   • Initialize a queue with start.

2. Traversal:

   • While the queue is not empty:
     • Dequeue the front node from the queue.
     • Add all its unvisited neighbors to the queue.
     • Mark each of these neighbors as visited to avoid processing them again.
     • Add the dequeued node to the result list.

3. Completion:

   • The algorithm completes when the queue is empty, meaning all nodes that can be reached from the starting node have been visited in level-order fashion.

Here's the implementation of this BFS algorithm:

package main

import "fmt"

func bfs(graph *Graph, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    result := []int{}

    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        result = append(result, node)
        for _, neighbor := range graph.GetAdjList()[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }

    return result
}

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

    traversal := bfs(graph, 0)
    for _, node := range traversal {
        fmt.Print(node, " ") // Output: 0 1 2 3 4 5
    }
}