Graph Representations in Lua

Graphs show up everywhere in programming. Social networks, road maps, dependency trees, game state machines — all are graphs underneath. A graph consists of vertices (nodes) and edges (connections between nodes). The problem is: how do you store a graph in Lua?

This tutorial covers the two standard representations — adjacency matrix and adjacency list — and shows you when to use each one. We’ll also implement Breadth-First Search (BFS) and Depth-First Search (DFS) so you can actually traverse the graphs you build.

Graphs in Lua

Before diving into code, let’s clarify the types of graphs you’ll encounter:

• Directed edges have a direction (A points to B, but not necessarily back).
• Undirected edges have no direction (A connects to B, and B connects to A).
• Weighted edges carry a value — a distance, cost, or priority.
• Unweighted edges simply exist or they don’t.

Lua has no built-in graph type. You build one using tables. The representation you choose affects how fast you can query edges, how much memory the graph consumes, and which algorithms are a natural fit.

Adjacency Matrix

An adjacency matrix is a two-dimensional table where matrix[u][v] tells you whether an edge runs from vertex u to vertex v. For unweighted graphs, you store true or false. For weighted graphs, you store the weight value directly.

Building a Matrix

local function new_matrix(n)
  local matrix = {}
  for i = 1, n do
    matrix[i] = {}
    for j = 1, n do
      matrix[i][j] = false
    end
  end
  return matrix
end

local function add_edge(matrix, u, v, weight)
  if weight then
    matrix[u][v] = weight
  else
    matrix[u][v] = true
  end
end

local function has_edge(matrix, u, v)
  return matrix[u][v] ~= false and matrix[u][v] ~= nil
end

-- Build a 4-vertex directed graph
local graph = new_matrix(4)
add_edge(graph, 1, 2)
add_edge(graph, 1, 3)
add_edge(graph, 2, 4)
add_edge(graph, 3, 4)

The matrix representation shines when you need to check whether an edge exists between any two vertices. Edge lookup is O(1) — you just index into the table. Adding or removing an edge is also O(1). The tradeoff is space: a matrix for n vertices always allocates n² table entries, even if the graph has only a handful of edges.

When a Matrix Makes Sense

If your graph is dense — most vertex pairs are connected — a matrix avoids the overhead of iterating through sparse neighbour lists. For small graphs where memory isn’t a concern, the simplicity is hard to beat. The matrix also makes it trivial to extend to weighted edges: just store the weight value instead of true.

-- Weighted adjacency matrix
local weighted = new_matrix(3)
add_edge(weighted, 1, 2, 10)
add_edge(weighted, 1, 3, 25)
add_edge(weighted, 2, 3, 5)

print(weighted[1][2])  --> 10
print(has_edge(weighted, 1, 2))  --> true

For anything sparse — and most real-world graphs are sparse — an adjacency list is the better choice.

Adjacency List

An adjacency list stores, for each vertex, only the neighbours it’s actually connected to. In Lua, this maps naturally to a table where each key is a vertex and the value is a set or sequence of its neighbours.

local function new_list(directed)
  return {
    directed = directed or false,
    adj = {},     -- adj[v] = set of neighbours
    vertices = {},  -- set of all known vertices (including isolated)
  }
end

local function add_vertex(g, v)
  if not g.adj[v] then
    g.adj[v] = {}
  end
  g.vertices[v] = true
end

local function add_edge(g, u, v)
  add_vertex(g, u)
  add_vertex(g, v)
  g.adj[u][v] = true
  if not g.directed then
    g.adj[v][u] = true
  end
end

local function has_edge(g, u, v)
  return g.adj[u] and g.adj[u][v] == true
end

local function neighbours(g, v)
  local result = {}
  if g.adj[v] then
    for neighbor, _ in pairs(g.adj[v]) do
      table.insert(result, neighbor)
    end
  end
  return result
end

local g = new_list(false)  -- undirected
add_edge(g, 1, 2)
add_edge(g, 1, 3)
add_edge(g, 2, 4)
add_edge(g, 3, 4)

print(table.concat(neighbours(g, 1), ", "))  --> 2, 3

The adjacency list uses O(V + E) space — proportional to the number of vertices plus edges. That’s a dramatic improvement over the matrix for sparse graphs. Iterating over neighbours of a vertex visits only the actual connections, not the entire row of a matrix.

The one drawback is edge lookup. To check whether (u, v) exists, you potentially need to scan through all of u’s neighbours. That’s O(deg(u)) in the worst case, which is fine in practice but slower than the O(1) matrix lookup.

Weighted Adjacency List

For weighted graphs, store the weight as the neighbour value instead of true:

local function add_weighted_edge(g, u, v, weight)
  add_vertex(g, u)
  add_vertex(g, v)
  g.adj[u][v] = weight
  if not g.directed then
    g.adj[v][u] = weight
  end
end

local function get_weight(g, u, v)
  return g.adj[u] and g.adj[u][v]
end

local weighted = new_list(true)
add_weighted_edge(weighted, 1, 2, 10)
add_weighted_edge(weighted, 1, 3, 25)
add_weighted_edge(weighted, 2, 3, 5)

print(get_weight(weighted, 1, 2))  --> 10

Comparing the Two Representations

Operation	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Edge lookup (u,v)	O(1)	O(deg(u)) average
Add edge	O(1)	O(1)
Iterate neighbours(v)	O(V)	O(deg(v))
Best for	Dense, static graphs	Sparse, dynamic graphs

The rule of thumb: if your graph has far fewer edges than V², use an adjacency list. It maps naturally to Lua tables and is the standard choice for most Lua graph code.

Breadth-First Search

BFS explores a graph level by level, visiting all nodes at distance 1 before distance 2, and so on. It uses a queue. BFS is the algorithm you reach for when you need shortest path in an unweighted graph.

Using the adjacency list from above, here’s BFS:

local function bfs(g, start)
  local visited = {}
  local queue = { start }
  local order = {}
  visited[start] = true

  while #queue > 0 do
    local v = table.remove(queue, 1)  -- dequeue front
    table.insert(order, v)

    for _, neighbor in ipairs(neighbours(g, v)) do
      if not visited[neighbor] then
        visited[neighbor] = true
        table.insert(queue, neighbor)  -- enqueue back
      end
    end
  end

  return order
end

local g = new_list(false)
add_edge(g, 1, 2)
add_edge(g, 1, 3)
add_edge(g, 2, 4)
add_edge(g, 3, 4)
add_edge(g, 2, 5)
add_edge(g, 3, 6)

print(table.concat(bfs(g, 1), " -> "))  --> 1 -> 2 -> 3 -> 4 -> 5 -> 6

If you also track the parent of each visited node, you can reconstruct the shortest path from start to any reachable vertex:

local function bfs_path(g, start, goal)
  local visited = {}
  local parent = {}
  local queue = { start }
  visited[start] = true

  while #queue > 0 do
    local v = table.remove(queue, 1)

    if v == goal then
      local path = {}
      local current = goal
      while current do
        table.insert(path, 1, current)
        current = parent[current]
      end
      return path
    end

    for _, neighbor in ipairs(neighbours(g, v)) do
      if not visited[neighbor] then
        visited[neighbor] = true
        parent[neighbor] = v
        table.insert(queue, neighbor)
      end
    end
  end

  return nil  -- goal not reachable
end

local path = bfs_path(g, 1, 5)
if path then
  print(table.concat(path, " -> "))  --> 1 -> 2 -> 5
end

BFS runs in O(V + E) time and uses O(V) space.

Depth-First Search

DFS dives deep along each branch before backtracking. It uses a stack, which you can implement iteratively or recursively using Lua’s standard call stack.

Iterative DFS using an explicit stack:

local function dfs_iterative(g, start)
  local visited = {}
  local stack = { start }
  local order = {}

  while #stack > 0 do
    local v = table.remove(stack)  -- pop
    if not visited[v] then
      visited[v] = true
      table.insert(order, v)

      -- Push neighbours in reverse order so leftmost is processed first
      local nbs = neighbours(g, v)
      for i = #nbs, 1, -1 do
        table.insert(stack, nbs[i])
      end
    end
  end

  return order
end

print(table.concat(dfs_iterative(g, 1), " -> "))

Recursive DFS lets you write the algorithm without managing a stack explicitly:

local function dfs_recursive(g, v, visited, order)
  visited[v] = true
  table.insert(order, v)

  for _, neighbor in ipairs(neighbours(g, v)) do
    if not visited[neighbor] then
      dfs_recursive(g, neighbor, visited, order)
    end
  end
end

local function dfs(g, start)
  local visited = {}
  local order = {}
  dfs_recursive(g, start, visited, order)

  -- Handle disconnected components by checking all known vertices
  for v, _ in pairs(g.vertices) do
    if not visited[v] then
      dfs_recursive(g, v, visited, order)
    end
  end

  return order
end

print(table.concat(dfs(g, 1), " -> "))

DFS is useful for cycle detection, topological sorting, and finding connected components. Like BFS, it runs in O(V + E) time.

Choosing Your Representation

Pick the representation based on what your graph looks like and what operations you perform most:

• Sparse graph, dynamic changes — adjacency list, O(V + E) space.
• Dense graph, many edge-existence queries — adjacency matrix, O(V²) space.
• Need shortest path — adjacency list + BFS.
• Cycle detection, topological sort — adjacency list + DFS.
• Weighted edges — both representations work; just store the weight value.

Conclusion

Lua tables give you everything you need to represent graphs. An adjacency matrix is dead simple and gives you O(1) edge lookups, but costs O(V²) space regardless of how many edges your graph actually has. An adjacency list uses space proportional to vertices and edges, iterates neighbours efficiently, and fits Lua’s table model like a glove. For most Lua graph work, the adjacency list is the right starting point.

With a list representation in hand, BFS and DFS are straightforward to implement. BFS finds shortest paths in unweighted graphs. DFS handles cycle detection, component discovery, and topological sorting.

See Also

• Tables in Lua — the foundation everything here is built on
• Arrays and Lists in Lua — sequences and the patterns you’ll use with adjacency lists
• Stacks and Queues in Lua — the data structures BFS and DFS are built on