Graph Data Structure Implementation and Traversal Algorithms (BFS and DFS) in Golang (With Examples)

Graphs are one of the most popular data structures used in programming, and for some, may seem like one of the most confusing.

This tutorial will help you understand the fundamentals of graphs, how to represent them as a data structure, and how you can implement graph traversal algorithms in Go.

If you want to skip the explanation and just see the code, you can find it here

Representing Graphs in Go

There are two components of graphs that you need to know for representing it: Nodes and Vertices.

  • A vertex represents a point in the graph, and can be identified by it's key.
  • An edge is a connection between two nodes
  • The edges may be directed (following direction), or undirected (with no direction)

graph structure

We can represent a vertex as a new struct :

type Vertex struct {
	// Key is the unique identifier of the vertex
	Key int
	// Vertices will describe vertices connected to this one
	// The key will be the Key value of the connected vertice
	// with the value being the pointer to it
	Vertices map[int]*Vertex
}

// We then create a constructor function for the Vertex
func NewVertex(key int) *Vertex {
	return &Vertex{
		Key:      key,
		Vertices: map[int]*Vertex{},
	}
}

Next, we can make a struct to represent the graph as a whole:

type Graph struct {
	// Vertices describes all vertices contained in the graph
	// The key will be the Key value of the connected vertice
	// with the value being the pointer to it
	Vertices map[int]*Vertex
	// This will decide if it's a directed or undirected graph
	directed bool
}

// We defined constructor functions that create
// new directed or undirected graphs respectively

func NewDirectedGraph() *Graph {
	return &Graph{
		Vertices: map[int]*Vertex{},
		directed: true,
	}
}

func NewUndirectedGraph() *Graph {
	return &Graph{
		Vertices: map[int]*Vertex{},
	}
}

Finally, let's add an AddVertex and AddEdge method that will allow us to add vertices to the graph and create edges between them:

// AddVertex creates a new vertex with the given
// key and adds it to the graph
func (g *Graph) AddVertex(key int) {
	v := NewVertex(key)
	g.Vertices[key] = v
}

// The AddEdge method adds an edge between two vertices in the graph
func (g *Graph) AddEdge(k1, k2 int) {
	v1 := g.Vertices[k1]
	v2 := g.Vertices[k2]

	// return an error if one of the vertices doesn't exist
	if v1 == nil || v2 == nil {
		panic("not all vertices exist")
	}

	// do nothing if the vertices are already connected
	if _, ok := v1.Vertices[v2.Key]; ok {
		return
	}

	// Add a directed edge between v1 and v2
	// If the graph is undirected, add a corresponding
	// edge back from v2 to v1, effectively making the
	// edge between v1 and v2 bidirectional
	v1.Vertices[v2.Key] = v2
	if !g.directed && v1.Key != v2.Key {
		v2.Vertices[v1.Key] = v1
	}

	// Add the vertices to the graph's vertex map
	g.Vertices[v1.Key] = v1
	g.Vertices[v2.Key] = v2
}

We can now create a graph by instantiating a new Graph struct and adding vertices and edges.

For example, if we had to create this directed graph:

example graph with four nodes

We could do so using the AddVertex and AddEdge methods:

g := graph.NewDirectedGraph()

g.AddVertex(1)
g.AddVertex(2)
g.AddVertex(3)
g.AddVertex(4)

g.AddEdge(1, 2)
g.AddEdge(2, 3)
g.AddEdge(2, 4)
g.AddEdge(4, 1)

Let's look at how to implement some common algorithms using the data structure we created.

Depth First Search (DFS)

"Search" algorithms are what allow us to traverse the entire graph from a single starting point. As the name suggests, depth first search traverses through all neighboring nodes recursively, so deeper nodes are traversed before adjacent nodes.

This can be best described by an illustration. Consider this sample graph:

sample-graph illustration

If we start with Node 1, we traverse each child node, and if the child node has any children, we traverse those first before going to a sister node:

dfs traversal order

Note that nodes 3 and 4 are never visited since they're disconnected from the starting node

Let's look at the Go code for implementing this:

// here, we import the graph we defined in the previous section as the `graph` package
func DFS(g *graph.Graph, startVertex *graph.Vertex, visitCb func(int)) {
	// we maintain a map of visited nodes to prevent visiting the same
	// node more than once
	visited := map[int]bool{}

	if startVertex == nil {
		return
	}
	visited[startVertex.Key] = true
	visitCb(startVertex.Key)

	// for each of the adjacent vertices, call the function recursively
	// if it hasn't yet been visited
	for _, v := range startVertex.Vertices {
		if visited[v.Key] {
			continue
		}
		DFS(g, v, visitCb)
	}
}

You can find the full working example here

Breadth First Search (BFS)

In breadth first search, we traverse all adjacent nodes of the current node before moving on to their children. This is a bit more complex than depth first search since we have to keep track of the child nodes that we want to traverse later.

We do this by using an additional queue data structure, that holds the list of nodes that need to be traversed.

If we consider the same example graph used in the last example, we can picture the traversal order and the queue as follows:

BFS traversal order

Every time we traverse a node, we enqueue its child nodes, and then move on to the next node in the queue

To express this algorithm in code, we'll create a minimal queue implementation:

// create a node that holds the graphs vertex as data
type node struct {
	v    *graph.Vertex
	next *node
}

// create a queue data structure
type queue struct {
	head *node
	tail *node
}

// enqueue adds a new node to the tail of the queue
func (q *queue) enqueue(v *graph.Vertex) {
	n := &node{v: v}

	// if the queue is empty, set the head and tail as the node value
	if q.tail == nil {
		q.head = n
		q.tail = n
		return
	}

	q.tail.next = n
	q.tail = n
}

// dequeue removes the head from the queue and returns it
func (q *queue) dequeue() *graph.Vertex {
	n := q.head
	// return nil, if head is empty
	if n == nil {
		return nil
	}

	q.head = q.head.next

	// if there wasn't any next node, that
	// means the queue is empty, and the tail
	// should be set to nil
	if q.head == nil {
		q.tail = nil
	}

	return n.v
}

We can then create a function for BFS traversal:

func BFS(g *graph.Graph, startVertex *graph.Vertex, visitCb func(int)) {
	// initialize queue and visited vertices map
	vertexQueue := &queue{}
	visitedVertices := map[int]bool{}

	currentVertex := startVertex
	// start a continuous loop
	for {
		// visit the current node
		visitCb(currentVertex.Key)
		visitedVertices[currentVertex.Key] = true

		// for each neighboring vertex, push it to the queue
		// if it isn't already visited
		for _, v := range currentVertex.Vertices {
			if !visitedVertices[v.Key] {
				vertexQueue.enqueue(v)
			}
		}

		// change the current vertex to the next one
		// in the queue
		currentVertex = vertexQueue.dequeue()
		// if the queue is empty, break out of the loop
		if currentVertex == nil {
			break
		}
	}
}

You can find the full working example here

If you feel like you've got the hang of BFS and DFS, let's test your knowledge!

Which node will be visited first?

Assuming we use BFS, which node would be visited first for this graph?

graph question sample

Node 9 will be visited before node 6.

With respect to node 1, node 6 is three levels deep, where are node 9 is only two levels deep. Using BFS, the order would be:

graph answer queue

You can find the complete source code, along with test cases on Github


Liked this article? Share it on: