# 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) 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: We could do so using the `AddVertex` and `AddEdge` methods:

``````g := graph.NewDirectedGraph()

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: 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: 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

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: 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 {
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.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 {
// return nil, if head is empty
if n == nil {
return nil
}

// if there wasn't any next node, that
// means the queue is empty, and the tail
// should be set to 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? 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: You can find the complete source code, along with test cases on Github