Graph Representations: How to Store Connections in Memory 📚

Now that you understand what graphs are, let’s explore different ways to store them in your computer’s memory. Just like you can organize your books in different ways (alphabetical, by color, by size), there are different ways to store graph connections in code.

Each representation has its own advantages and disadvantages, so choosing the right one depends on what you want to do with your graph!

Method 1: Adjacency List (Most Common) 📝

An adjacency list is like each person having a list of their friends. This is the most common way to store graphs because it’s memory-efficient and fast for most operations.

package main

import "fmt"

// Adjacency List representation
type Graph struct {
    vertices int           // Number of nodes
    adjList  [][]int       // For each vertex, list of connected vertices
}

func NewGraph(vertices int) *Graph {
    return &Graph{
        vertices: vertices,
        adjList:  make([][]int, vertices),
    }
}

func (g *Graph) AddEdge(from, to int) {
    // Add edge from -> to
    g.adjList[from] = append(g.adjList[from], to)

    // For undirected graphs, also add reverse edge
    // g.adjList[to] = append(g.adjList[to], from)
}

func (g *Graph) GetNeighbors(vertex int) []int {
    return g.adjList[vertex]
}

func (g *Graph) PrintGraph() {
    for i := 0; i < g.vertices; i++ {
        fmt.Printf("Vertex %d: ", i)
        for _, neighbor := range g.adjList[i] {
            fmt.Printf("%d ", neighbor)
        }
        fmt.Println()
    }
}

func main() {
    // Create a graph with 5 vertices
    g := NewGraph(5)

    // Add edges (undirected graph)
    g.AddEdge(0, 1)
    g.AddEdge(0, 4)
    g.AddEdge(1, 2)
    g.AddEdge(1, 3)
    g.AddEdge(1, 4)
    g.AddEdge(2, 3)
    g.AddEdge(3, 4)

    // Add reverse edges for undirected graph
    g.AddEdge(1, 0)
    g.AddEdge(4, 0)
    g.AddEdge(2, 1)
    g.AddEdge(3, 1)
    g.AddEdge(4, 1)
    g.AddEdge(3, 2)
    g.AddEdge(4, 3)

    g.PrintGraph()
    // Output:
    // Vertex 0: 1 4
    // Vertex 1: 2 3 4 0
    // Vertex 2: 3 1
    // Vertex 3: 4 1 2
    // Vertex 4: 0 1 3
}

Pros of Adjacency List:

Memory efficient (only stores existing connections)
Fast to iterate through neighbors
Easy to add/remove edges

Cons of Adjacency List:

Slower to check if two vertices are connected
Not great for dense graphs

Method 2: Adjacency Matrix (Easy to Understand) 📊

An adjacency matrix is like a big grid where rows and columns represent vertices, and a 1 means “connected”, 0 means “not connected”.

package main

import "fmt"

// Adjacency Matrix representation
type MatrixGraph struct {
    vertices int
    matrix   [][]int // 2D grid of connections
}

func NewMatrixGraph(vertices int) *MatrixGraph {
    matrix := make([][]int, vertices)
    for i := range matrix {
        matrix[i] = make([]int, vertices)
    }

    return &MatrixGraph{
        vertices: vertices,
        matrix:   matrix,
    }
}

func (mg *MatrixGraph) AddEdge(from, to int) {
    mg.matrix[from][to] = 1

    // For undirected graphs
    mg.matrix[to][from] = 1
}

func (mg *MatrixGraph) IsConnected(from, to int) bool {
    return mg.matrix[from][to] == 1
}

func (mg *MatrixGraph) GetDegree(vertex int) int {
    degree := 0
    for i := 0; i < mg.vertices; i++ {
        if mg.matrix[vertex][i] == 1 {
            degree++
        }
    }
    return degree
}

func (mg *MatrixGraph) PrintMatrix() {
    for i := 0; i < mg.vertices; i++ {
        for j := 0; j < mg.vertices; j++ {
            fmt.Printf("%d ", mg.matrix[i][j])
        }
        fmt.Println()
    }
}

func main() {
    mg := NewMatrixGraph(4)

    // Add edges
    mg.AddEdge(0, 1)
    mg.AddEdge(0, 2)
    mg.AddEdge(1, 2)
    mg.AddEdge(2, 3)

    fmt.Println("Adjacency Matrix:")
    mg.PrintMatrix()
    // Output:
    // 0 1 1 0
    // 1 0 1 0
    // 1 1 0 1
    // 0 0 1 0

    fmt.Printf("Is 0 connected to 2? %t\n", mg.IsConnected(0, 2)) // true
    fmt.Printf("Degree of vertex 2: %d\n", mg.GetDegree(2)) // 3
}

Pros of Adjacency Matrix:

Very fast to check if two vertices are connected
Simple to understand and implement
Good for dense graphs

Cons of Adjacency Matrix:

Uses lots of memory (especially for sparse graphs)
Slower to find all neighbors of a vertex
Fixed size - can’t easily add new vertices

Method 3: Edge List (Simple Storage) 📋

An edge list is just a list of all the connections in the graph. Simple but not very efficient for most operations.

package main

import "fmt"

// Edge representation
type Edge struct {
    From, To int
}

// Edge List representation
type EdgeListGraph struct {
    vertices int
    edges    []Edge
}

func NewEdgeListGraph(vertices int) *EdgeListGraph {
    return &EdgeListGraph{
        vertices: vertices,
        edges:    make([]Edge, 0),
    }
}

func (elg *EdgeListGraph) AddEdge(from, to int) {
    elg.edges = append(elg.edges, Edge{from, to})

    // For undirected graphs
    elg.edges = append(elg.edges, Edge{to, from})
}

func (elg *EdgeListGraph) GetAllEdges() []Edge {
    return elg.edges
}

func (elg *EdgeListGraph) CountEdges() int {
    return len(elg.edges)
}

func main() {
    elg := NewEdgeListGraph(4)

    elg.AddEdge(0, 1)
    elg.AddEdge(0, 2)
    elg.AddEdge(1, 2)
    elg.AddEdge(2, 3)

    fmt.Printf("Total edges: %d\n", elg.CountEdges())
    fmt.Println("All edges:")
    for _, edge := range elg.GetAllEdges() {
        fmt.Printf("%d -> %d\n", edge.From, edge.To)
    }
}

Method 4: Weighted Graphs (With Costs/Distances) ⚖️

Sometimes connections have weights - like distances between cities or costs of flights.

package main

import "fmt"

// Weighted Edge
type WeightedEdge struct {
    From, To, Weight int
}

// Weighted Adjacency List
type WeightedGraph struct {
    vertices int
    adjList  [][]WeightedEdge
}

func NewWeightedGraph(vertices int) *WeightedGraph {
    return &WeightedGraph{
        vertices: vertices,
        adjList:  make([][]WeightedEdge, vertices),
    }
}

func (wg *WeightedGraph) AddWeightedEdge(from, to, weight int) {
    wg.adjList[from] = append(wg.adjList[from], WeightedEdge{from, to, weight})

    // For undirected weighted graphs
    wg.adjList[to] = append(wg.adjList[to], WeightedEdge{to, from, weight})
}

func (wg *WeightedGraph) GetWeightedNeighbors(vertex int) []WeightedEdge {
    return wg.adjList[vertex]
}

func main() {
    wg := NewWeightedGraph(4)

    // Add weighted edges (flight costs)
    wg.AddWeightedEdge(0, 1, 100) // NYC to Boston: $100
    wg.AddWeightedEdge(0, 2, 500) // NYC to LA: $500
    wg.AddWeightedEdge(1, 2, 400) // Boston to LA: $400
    wg.AddWeightedEdge(2, 3, 200) // LA to Seattle: $200

    fmt.Println("Flights from NYC (0):")
    for _, edge := range wg.GetWeightedNeighbors(0) {
        fmt.Printf("To city %d: $%d\n", edge.To, edge.Weight)
    }
}

Choosing the Right Representation 🎯

Use Case	Best Representation	Why
Sparse graph (few connections)	Adjacency List	Memory efficient
Dense graph (many connections)	Adjacency Matrix	Fast lookups
Need to store edge weights	Weighted Adjacency List	Natural fit
Simple storage	Edge List	Minimal memory
Need fast connectivity checks	Adjacency Matrix	O(1) lookup
Need to iterate neighbors often	Adjacency List	Fast iteration

Real-World Examples 🌍

socialGraph := NewGraph(1000000) // 1 million users
// Most users have <100 friends, so adjacency list saves memory

Flight Network (Dense) → Adjacency Matrix

flightMatrix := NewMatrixGraph(100) // 100 airports
// Many airports connect to many others, matrix is fine

Road Network (Weighted) → Weighted Adjacency List

roadGraph := NewWeightedGraph(50000) // 50k intersections
// Each road has distance/length as weight

Practice Problems 🎯

Memory Comparison: Compare memory usage of adjacency list vs matrix for a graph with 100 vertices and 200 edges
Fastest Check: Which representation is fastest to check if vertex A connects to vertex B?
Neighbor Iteration: Which representation is fastest to list all friends of a person?
Weighted Social: Modify the friendship graph to include “closeness” weights (1-10)

What’s Next? 🚀

Now that you know how to store graphs in memory, the next lesson will teach you how to traverse graphs - visiting all the nodes in different orders. We’ll learn Breadth-First Search (BFS) and Depth-First Search (DFS), which are fundamental graph algorithms!

Understanding graph representations is crucial because it affects the efficiency of all your graph algorithms. Choose wisely based on your use case! 📊

Popular Topics

Categories