A graph is a set of vertices connected by edges. Edges may be:

  • Directed (arrows) or undirected (lines).
  • Weighted (edge has a number) or unweighted.

Graphs are everywhere: road maps, web pages and links, social networks, build-system DAGs, file dependencies, network routing, finite state machines.

Representations

Representation Space "Are u, v connected?" "Iterate neighbors of u" Best for
Adjacency matrix O(V²) O(1) O(V) Dense graphs.
Adjacency list O(V + E) O(deg u) O(deg u) Sparse graphs.
Edge list O(E) O(E) O(E) Algorithms that just iterate edges (Kruskal).

We use adjacency lists ([][]int for unweighted, [][]edge for weighted). Vertices are integers in [0, n).

Algorithms in this chapter

Breadth-first search (BFS)

Visits vertices in order of distance from the source. Uses a queue. Use it for: shortest path in unweighted graphs, level-order traversal, finding connected components, word-ladder puzzles.

Complexity: O(V + E).

Depth-first search (DFS)

Goes as deep as possible before backtracking. Recursive or with an explicit stack. Use it for: cycle detection, topological sort, strongly connected components, maze generation, finding bridges and articulation points.

Complexity: O(V + E).

Topological sort (Kahn's algorithm)

For a DAG (directed acyclic graph), a topological order is a linear ordering of vertices such that every edge u -> v has u before v.

Kahn's algorithm: repeatedly take a vertex with in-degree 0, remove it, and decrement its neighbors' in-degrees. If you finish before processing all vertices, the graph has a cycle.

Complexity: O(V + E).

Dijkstra's shortest path

For graphs with non-negative edge weights, finds the shortest path from a source to every other vertex. Uses a min-priority queue.

Complexity: O((V + E) log V) with a binary heap.

For graphs with negative weights use Bellman-Ford instead (not implemented here; left as an exercise).

What we implement

graph.Graph — directed graph with integer vertices, methods:

  • AddEdge(u, v int)
  • Vertices() int
  • Neighbors(u int) []int
  • BFS(src int, visit func(int))
  • DFSIter(src int, visit func(int)) (iterative, with an explicit stack)
  • DFSRec(src int, visit func(int)) (recursive, for comparison)
  • TopologicalSort() ([]int, bool) — false if cyclic.

graph.WeightedGraph — same idea, weighted edges, with:

  • AddEdge(u, v, w int)
  • Dijkstra(src int) (dist []int, prev []int)

Run the tests

go test ./part2-dsa/ds/graph