Graph Structure in Go

Before diving into the algorithms, we need a way to represent graphs. A common approach is to use an adjacency list. Below is a simple implementation of a graph structure in Go.

package main

import "fmt"

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

// NewGraph creates a new graph.
func NewGraph() *Graph {
	return &Graph{vertices: make(map[int][]int)}
}

// AddEdge adds a directed edge from vertex u to vertex v.
func (g *Graph) AddEdge(u, v int) {
	g.vertices[u] = append(g.vertices[u], v)
}

// GetVertices returns the vertices in the graph.
func (g *Graph) GetVertices() []int {
	vertices := make([]int, 0, len(g.vertices))
	for v := range g.vertices {
		vertices = append(vertices, v)
	}
	return vertices
}

Explanation

  • Graph Structure: The Graph struct contains a map where keys are vertices and values are slices of integers representing adjacent vertices.
  • AddEdge Method: This method allows adding directed edges to the graph.
  • GetVertices Method: This method retrieves all vertices in the graph.

Depth-First Search (DFS)

DFS is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. Below is an implementation of DFS in Go.

// DFS performs a depth-first search on the graph.
func (g *Graph) DFS(start int, visited map[int]bool) {
	// Mark the current node as visited
	visited[start] = true
	fmt.Printf("%d ", start)

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

// DFSWrapper is a helper function to initiate DFS.
func (g *Graph) DFSWrapper(start int) {
	visited := make(map[int]bool)
	g.DFS(start, visited)
}

Explanation

  • DFS Method: This method marks the current vertex as visited and recursively visits all unvisited adjacent vertices.
  • DFSWrapper Method: This helper function initializes the visited map and starts the DFS from a given vertex.

Breadth-First Search (BFS)

BFS is another traversal algorithm that explores all neighbors at the present depth prior to moving on to nodes at the next depth level. Below is an implementation of BFS in Go.

import "container/list"

// BFS performs a breadth-first search on the graph.
func (g *Graph) BFS(start int) {
	visited := make(map[int]bool)
	queue := list.New()

	// Mark the starting node as visited and enqueue it
	visited[start] = true
	queue.PushBack(start)

	for queue.Len() > 0 {
		// Dequeue a vertex from the queue
		current := queue.Front()
		queue.Remove(current)
		fmt.Printf("%d ", current.Value)

		// Get all adjacent vertices of the dequeued vertex
		for _, neighbor := range g.vertices[current.Value.(int)] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue.PushBack(neighbor)
			}
		}
	}
}

Explanation

  • BFS Method: This method uses a queue to keep track of vertices to visit. It marks a vertex as visited and enqueues its unvisited neighbors.

Example Usage

Here is how you can use the Graph struct and the DFS and BFS methods:

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

	fmt.Println("DFS starting from vertex 2:")
	graph.DFSWrapper(2)

	fmt.Println("\nBFS starting from vertex 2:")
	graph.BFS(2)
}

Output

When you run the above code, you should see output similar to this:

DFS starting from vertex 2:
2 0 1 3 
BFS starting from vertex 2:
2 0 3 1

Conclusion

In this tutorial, we covered how to implement a simple graph structure in Go and explored two fundamental graph traversal algorithms: Depth-First Search and Breadth-First Search. These algorithms are widely used in various applications, including social network analysis, web crawling, and more.

By leveraging Go's concurrency and efficiency, you can further enhance these algorithms to handle larger datasets and more complex graph structures.

Learn more with useful resources