A journey through graph theory fundamentals—vertices, edges, representations, and traversal algorithms—with a complete implementation in Go.

I. The Language of Connections

Graph theory is the mathematics of relationships. It concerns itself with objects and the connections between them—nothing more, nothing less. Yet from this austere foundation emerges a framework capable of modeling social networks, road systems, molecular structures, the internet, and nearly any domain where entities relate to one another.

A graph $G$ is defined as an ordered pair $G = (V, E)$ where:

• $V$ is a set of vertices (also called nodes)
• $E$ is a set of edges (also called links or arcs)

Each edge connects two vertices. In an undirected graph, the edge $\{u, v\}$ is identical to $\{v, u\}$—the connection has no inherent direction. In a directed graph (or digraph), the edge $(u, v)$ is distinct from $(v, u)$—one points from $u$ to $v$, the other from $v$ to $u$.

Consider a simple example: five people at a party, some of whom know each other. Each person is a vertex. Each acquaintance is an edge. The resulting graph captures the social structure of the room without requiring names, ages, or any other attribute—pure topology.

II. Graph Representations

A graph exists as an abstract mathematical object. To compute with it, we need concrete representations.

The Adjacency Matrix

For a graph with $n$ vertices, the adjacency matrix $A$ is an $n \times n$ matrix where:

For an undirected graph, the matrix is symmetric: $A_{ij} = A_{ji}$. For a directed graph, this symmetry does not generally hold.

The adjacency matrix excels at edge lookup—determining whether two vertices connect requires only a single array access, $O(1)$ time. But it consumes $O(n^2)$ space regardless of the number of edges, making it inefficient for sparse graphs where most potential edges do not exist.

The Adjacency List

The adjacency list represents each vertex alongside a list of its neighbors. For vertex $v$, we maintain a collection of all vertices $u$ such that an edge $(v, u)$ exists.

Space complexity drops to $O(n + m)$ where $m$ is the number of edges—a significant improvement for sparse graphs. Edge lookup becomes $O(\text{degree}(v))$ rather than $O(1)$, but iterating over a vertex’s neighbors becomes more efficient.

The choice between representations depends on the graph’s density and the operations required. Dense graphs favor matrices; sparse graphs favor lists.

III. Traversal: Exploring the Graph

Given a starting vertex, how do we systematically visit every reachable vertex? Two fundamental strategies exist.

Depth-First Search (DFS)

Depth-first search explores as far as possible along each branch before backtracking. It proceeds with a kind of reckless curiosity—plunging deep into the graph, retreating only when no unvisited neighbors remain.

The algorithm:

1. Mark the starting vertex as visited
2. For each unvisited neighbor, recursively perform DFS
3. Backtrack when all neighbors have been visited

DFS naturally lends itself to recursive implementation. It uses $O(n)$ space for the recursion stack (in the worst case) and $O(n + m)$ time to visit all vertices and examine all edges.

Breadth-First Search (BFS)

Breadth-first search explores all neighbors at the current depth before proceeding to the next level. It expands outward in concentric circles from the starting vertex.

The algorithm:

1. Enqueue the starting vertex and mark it visited
2. While the queue is not empty:
   • Dequeue a vertex $v$
   • For each unvisited neighbor $u$, mark it visited and enqueue it

BFS requires an explicit queue but avoids deep recursion. It guarantees finding the shortest path (in terms of edge count) between the starting vertex and any reachable vertex—a property DFS does not share.

IV. Connected Components

A connected component is a maximal set of vertices such that a path exists between every pair. In an undirected graph, the vertices partition into disjoint connected components—islands of mutual reachability separated by the absence of edges.

Counting connected components reveals the graph’s fundamental structure. A social network might fragment into distinct communities. A road system might contain isolated regions. The count answers the question: How many separate pieces does this graph contain?

The algorithm is elegant:

1. Initialize a counter to zero
2. For each vertex $v$ in the graph:
   • If $v$ has not been visited:
     • Increment the counter
     • Perform DFS (or BFS) from $v$, marking all reachable vertices as visited
3. Return the counter

Each traversal discovers an entire connected component. The number of traversals initiated equals the number of components.

V. Implementation in Go

Theory crystallizes into code. The following implementation in Go demonstrates these concepts with explicit simplicity.

The Data Structures

type Edge struct {
    A string
    B string
}

type Graph struct {
    isDirected bool
    Nodes      []string
    Edges      []Edge
}

A graph consists of nodes (represented as strings for readability) and edges (pairs of node identifiers). The isDirected flag determines whether edges are bidirectional.

The Adjacency Matrix

func (g *Graph) GetAdjacencyMatrix() map[string]map[string]int {
    matrix := make(map[string]map[string]int)

    // Initialize all entries to 0
    for _, node := range g.Nodes {
        matrix[node] = make(map[string]int)
        for _, other := range g.Nodes {
            matrix[node][other] = 0
        }
    }

    // Mark edges as 1
    for _, edge := range g.Edges {
        matrix[edge.A][edge.B] = 1
        if !g.isDirected {
            matrix[edge.B][edge.A] = 1
        }
    }

    return matrix
}

Go’s maps provide flexible indexing by node name rather than requiring integer indices.

The Adjacency List

func (g *Graph) GetAdjacencyList() map[string][]string {
    list := make(map[string][]string)

    for _, node := range g.Nodes {
        list[node] = []string{}
    }

    for _, edge := range g.Edges {
        list[edge.A] = append(list[edge.A], edge.B)
        if !g.isDirected {
            list[edge.B] = append(list[edge.B], edge.A)
        }
    }

    return list
}

Each node maps to a slice of its neighbors—direct, efficient, and idiomatic Go.

Counting Connected Components

func (g *Graph) GetConnectedGroupsCount() int {
    visited := make(map[string]bool)
    adjList := g.GetAdjacencyList()
    count := 0

    for _, node := range g.Nodes {
        if !visited[node] {
            count++
            g.dfs(node, visited, adjList)
        }
    }

    return count
}

func (g *Graph) dfs(node string, visited map[string]bool, adjList map[string][]string) {
    visited[node] = true
    for _, neighbor := range adjList[node] {
        if !visited[neighbor] {
            g.dfs(neighbor, visited, adjList)
        }
    }
}

The depth-first search marks vertices as visited, preventing revisitation. Each call to dfs from the main loop discovers a new connected component.

VI. Example: Counting Groups

Consider a graph with ten nodes and the following edges:

nodes := []string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"}
edges := []Edge{
    {"A", "B"}, {"A", "C"}, {"B", "D"},
    {"E", "E"},  // self-loop
    {"F", "G"}, {"G", "H"},
    {"I", "J"},
}

Visualizing the structure:

• Component 1: A—B—D, A—C (nodes A, B, C, D form a connected group)
• Component 2: E alone (the self-loop does not connect it to others)
• Component 3: F—G—H (a chain of three)
• Component 4: I—J (a pair)

The algorithm correctly returns 4 connected components.

VII. Beyond the Basics

Graph theory extends far beyond connected components. Shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) find optimal routes through weighted graphs. Minimum spanning trees (Prim, Kruskal) extract the cheapest subgraph connecting all vertices. Topological sorting orders vertices in directed acyclic graphs. Network flow algorithms maximize throughput through capacitated edges.

Each algorithm builds upon the foundations explored here: vertices, edges, representations, traversal. The abstractions remain constant; only the questions change.

The implementation presented here—available on GitHub—serves as a starting point. Fork it. Extend it. Add weighted edges, implement BFS, compute shortest paths. Graph theory rewards exploration, and code is the laboratory where theory meets practice.

VIII. Reflections

There is a peculiar satisfaction in reducing complexity to structure. A social network with millions of users, billions of connections, infinite human drama—and graph theory sees only vertices and edges. This reductionism is not impoverishment but clarification. By stripping away the particular, we expose the universal.

The same algorithms that count friend groups on social media can identify isolated components in circuit boards, detect communities in protein interaction networks, or partition tasks in parallel computing systems. The mathematics does not care about the domain. It cares only about the relationships.

To implement a graph from scratch is to understand this abstraction at its foundation. Not as a black box invoked from a library, but as a structure you have built, traversed, and queried yourself. The code becomes a form of knowledge—executable, testable, yours.

Graph Theory: From Mathematics to Go Implementation

A journey through graph theory fundamentals—vertices, edges, representations, and traversal algorithms—with a complete implementation in Go.

Achraf SOLTANI — September 14, 2022