Table of Contents
Graphs in Go
This article was made for a youtube video, if you want to check that out: https://www.youtube.com/watch?v=bnnshkfNegU
What’s up engineers! Today we’re diving deep into something that’s everywhere around us, but most people don’t even realize it - Graphs.
Now, before you think this is just another boring d-ata structure, stick with me because graphs are literally the backbone of the modern world.
Every time you use Google Maps to find the shortest route, you are using a Graph Algorithm. Most recommendations algorithms like Netflix recommendation system and other streaming services. Social media showing you friends of friends uses graphs. Even the internet itself it’s just one massive graph.
In this video, we’re going to skip the heavy theory and focus on the practical side of graphs, we will learn the core principles about each function before in pseudocode and then implement it in Go from scratch. I’m going to explain why we make each design decision, when to use different representations in your structure and how the big O complexity impacts your real-world applications.
By the end of this video, you’ll understand:
- How to represent graphs in Go
- When to choose between matrices of values, adjacency list and adjacency matrix
- Why Go’s maps and pointers make graph implementation surprisingly elegant
- The methods: AddVertex, AddEdge, GetNeighbors, HasEdge and Remove Edge
- The Big O implications of every operation we implement
Ways to Represent Graphs in Go
Alright, when you’re implementing graphs in Go, you’ve got three main approaches, and choosing the wrong one can not only be a pain to implement but also have a huge impact on your performance.
Adjacency matrix Approach
This approach doesn’t need context, because it defines the vertices and edges.
Think of it like a 2D grid table where each cell tells you if two vertices are connected, that means that an intersection between a line and a column represents if there exists an edge between two vertices. So if you have vertices 1,2 and 3, you’d have a 3x3 matrix. The position [1][3] tells you if vertex 1 connects to vertex 3.
This approach might be great for edge lookups, checking if two vertices are connected is O(1).
However, this might not be ideal for Sparse graphs, if you have 1000 vertices and only 50 edges, you are wasting massive amounts of memory storing mostly zeros. So not the best use of Space Complexity, which is V².
Let’s see the big O Analysis of this approach.
Matrix of Values (Value Grid)
This approach looks like an adjacency matrix. However, each cell in the matrix is a vertex, which means it contains actual data, and edges are implicit based on spatial relationship.
How edges work
- Edges exist between adjacent cells based on problem context
- No explicit storage of edges - they’re determined by position
- Context determines valid movements/connections
Great for:
- Spatial Problems:
Pathfinding in games (2D/3D grids)
Image processing (pixel neighborhoods)
Maze solving algorithms
Cellular automata (Conway’s Game of Life)
- Geographic/Map Data:
GPS navigation on city grids
Terrain analysis
Resource allocation on maps
- Puzzle Games:
Sliding puzzles
Match-3 games
Board game AI
Let’s see the big O Analysis of this approach.
Adjacency List (our approach)
In languages like Java or C++, you’d typically use arrays or vectors. But Go gives us something beautiful - maps with pointer receivers, which makes everything easy to work with.
In this case, each vertex knows about its own connections. Think of it like a social network where each person has their own contact list.
Graph: This structure will contain a map of all the keys of all vertices.
Vertex: This structure will hold the data of a vertex. In our case an int value and a map of edges.
Edges: It’s the structure which holds the connection between two vertices. In this case, the weight of the edge and the destination vertex.
How It Works:
-
Graph.Vertices: find any vertex in O(1)
-
Vertex.edges: find any vertex neighbor in O(1)
-
Edge.dest: Direct pointer, no secondary lookups needed
Let’s see the big O of this.
Implementing the Graph
Now that we know the possible ways to make graphs in Go, let’s understand step by step the logic of each function and then implement it in code.
Let’s start by implementing the base structure of our Graph.
type IGraph interface {
AddVertex(d int) *Graph
AddEdge(from, to, weight int) *Edge
GetVertex(d int) *Vertex
GetNeighbors(vertex int) []int
HasAnyEdge(from int) bool
HasEdge(from, to int) bool
HasPath(from, to int) bool
RemoveEdge(from, to int) bool
PrintGraph()
}
type Graph struct {
// vertices vai conter um map das chaves de todos os vértices
Vertices map[int]*Vertex
}
type Edge struct {
weight int
dest *Vertex
}
type Vertex struct {
val int
// vertex key -> Edge
edges map[int]*Edge
}
func NewGraph() IGraph {
return &Graph{
Vertices: make(map[int]*Vertex),
}
}
Adding a vertex inside our graph
The steps to add a graph will be:
Step 1: Check if vertex exists Step 2: Create the new Vertex structure, without connections Step 3: Register the vertex in the graph (Vertices map)
The pseudocode will be like:
Now, lets implement this in Go
func (g *Graph) AddVertex(d int) *Graph {
// 1 - se já existir, não cria, retorna o grafo para ficar idempotente
if _, exists := g.Vertices[d]; exists {
return g
}
// 2 - vertex novo, sem nenhuma conexao ainda...
vertex := &Vertex{
val: d,
edges: make(map[int]*Edge),
}
// 3 - registrar no grafo, adiciona o novo vertice nos vertices
g.Vertices[d] = vertex
return g
}
Adding an edge
The adding edge function is an important one, because it transforms isolated vertices into a connected network. As we are implementing a directed graph, we will add only one way.
Step 1: Check if both to and from vertex exists Step 2: Check if edge already exists Step 3: Create the Edge Step 4: Store the Edge
func (g *Graph) AddEdge(from, to, weight int) *Edge {
// 1 - verificar se ambos os vertices existem
if g.GetVertex(from) == nil || g.GetVertex(to) == nil {
fmt.Printf("From or to doesnt exist")
return nil
}
// 2 - verificar se a aresta ja existe (apenas nesse vértice) - precisamos fazer apenas no vértice FROM (de destino)
// se queremos adicionar na aresta 1 -> 10, precisamos olhar apenas nas arestas do vértice 1
fromVertex := g.GetVertex(from)
var edge *Edge
if oldEdge, exists := fromVertex.edges[to]; exists {
edge = &Edge{
weight: weight,
dest: oldEdge.dest,
}
} else {
edge = &Edge{
weight: weight,
dest: g.GetVertex(to),
}
}
// 3 - Armazena o valor no map de arestas do vertice FROM
fromVertex.edges[to] = edge
return edge
}
Getting Neighbors
This is a crucial function, because it allows us to perform:
-
Algorithms that actually can check for paths inside our graphs, like BFS or DFS
-
Pathfinding: which are the options from this position
-
Shortest path: explore all reachable vertices with their distances
-
Graph Coloring
The steps are actually simple
Step 1: Check if vertex is nil
Step 2: range through the edges of the target vertex, and get each one key, which is basically the destination vertex
Step 3: Push each key to an array and return it by the end.
Let’s see how the pseudocode of that will be.
func (g *Graph) GetNeighbors(vertex int) []int {
// 1 - verificar se o vertex existe
targetVertex := g.GetVertex(vertex)
if targetVertex == nil {
return []int{}
}
// 2 - verificar o map de arestas e ver se tem algo
var neighbors []int
for k := range targetVertex.edges {
neighbors = append(neighbors, k)
}
return neighbors
}
Has Edge
In this function we will check if two vertices have edges between each other.
Step 1: Validate both vertices exist Step 2: Check the connection from vertex’s edge map and search for to key Step 3: Return the result
Let’s see how the pseudocode looks like.
func (g *Graph) HasEdge(from, to int) bool {
fromVertex := g.GetVertex(from)
toVertex := g.GetVertex(to)
if fromVertex == nil || toVertex == nil {
return false
}
if _, exists := fromVertex.edges[to]; exists {
return true
}
return false
}
Remove Edge
Step 1: Validate both vertices exist Step 2: Check if edge actually exists Step 3: Remove the edge
Let’s see how the pseudocode looks like.
func (g *Graph) RemoveEdge(from, to int) bool {
fromVertex := g.GetVertex(from)
toVertex := g.GetVertex(to)
if fromVertex == nil || toVertex == nil {
return false
}
if _, exists := fromVertex.edges[to]; exists {
delete(fromVertex.edges, to)
return true
}
return false
}
func (g *Graph) PrintGraph() {
if g == nil {
return
}
for k, v := range g.Vertices {
fmt.Printf("Vertex - Key: %d Value: %v", k, *v)
for _, val := range v.edges {
if val != nil {
fmt.Printf(" -> connected to vertex %v with weight %d", val.dest, val.weight)
} else {
fmt.Printf(" without connections")
}
}
fmt.Printf("\n")
}
}