mitchellh/zig-graph

---

mitchellh/zig-graph.json

{
  "createdAt": "2021-12-17T21:06:40Z",
  "defaultBranch": "main",
  "description": "Directed graph data structure for Zig",
  "fullName": "mitchellh/zig-graph",
  "homepage": null,
  "language": "Zig",
  "name": "zig-graph",
  "pushedAt": "2022-09-13T21:01:06Z",
  "stargazersCount": 111,
  "topics": [],
  "updatedAt": "2025-11-11T16:27:15Z",
  "url": "https://github.com/mitchellh/zig-graph"
}

zig-graph

A Zig library for directed graph data structures and associated algorithms. This library can be used for acyclic and cyclic graphs and unweighted and weighted edges. This library requires Zig 0.9+.

Warning: This is literally the first piece of Zig code I’ve ever written in my life. I’m using this project as a way to learn how to do things in Zig, what is idiomatic, what isn’t, etc. Feedback is very welcome on how I can improve and I expect to alter the library a bit as I do so. There is also a lot of room for improvement in performance by various measures.

Features

• Directed edges
• Cycle detection
• Strongly connected components
• Cheap edge reversal
• Depth-first traversal

TODO

• Vertex iterator
• Edge iterator
• Dijkstra for single-source shortest path w/ edge-weighting
• Kahn for topological sorting
• Shortest path given a topological sort
• String marshaling for easier debugging
• “Unmanaged” graph so allocator can be sent to each op

Example

const std = @import("std");
const graph = @import("graph");

pub fn main() void {
  // Create a directed graph type for strings.
  const Graph = graph.DirectedGraph([]const u8, std.hash_map.StringContext);

  // Initialize using some allocator
  var g = Graph.init(std.debug.global_allocator);
  defer g.deinit();

  // Add some vertices
  try g.add("A");
  try g.add("B");
  try g.add("C");

  // Add some edges with weights. For unweighted edges just make all
  // weights the same value.
  try g.addEdge("A", "B", 5);
  try g.addEdge("A", "C", 2);
  try g.addEdge("B", "C", 2);
  try g.addEdge("C", "B", 3);

  // We can detect cycles
  if (g.cycles()) |cycles| {
    defer cycles.deinit();
    std.log.info("there are {d} cycles", .{cycles.count()});
    return;
  }

  // We can do a depth-first search through iteration.
  var dfsIter = try g.dfsIterator("B");
  while (dfsIter.next()) |id| {
    std.log.info("{}", .{g.lookup(id).?});
  }
  dfsIter.deinit();

  // We can easily reverse the graph if we want.
  const reversed = g.reverse();

  // ... and more
}