Graphs and how to store them

A tree has one root and every node has one parent. Many real networks are messier: roads connect places in loops, a task can depend on several other tasks, a beam is connected to two columns and three secondary beams. A graph is the general model for “things and the connections between them”, and the rest of this module is about the algorithms that work on it.

The vocabulary

A tree is just a special graph: connected, with no cycles, and exactly V − 1 edges.

Graphs are everywhere: road and rail networks, the internet, project dependencies in a .NET solution, task schedules, social networks, electrical circuits, pipe networks, and the connections between elements in a structural model.

Adjacency list: each vertex knows its neighbours

The most common representation: for every vertex, a list of its neighbours (with weights if needed). It uses memory proportional to V + E and lists a vertex’s neighbours directly, which is exactly what most algorithms need.

1var roads = new Dictionary<string, List<(string To, int Minutes)>>();2 3void AddRoad(string a, string b, int minutes)4{5    if (!roads.ContainsKey(a)) roads[a] = new();6    if (!roads.ContainsKey(b)) roads[b] = new();7    roads[a].Add((b, minutes));          // undirected: store both directions8    roads[b].Add((a, minutes));9}10 11AddRoad("Gate", "Store", 4);12AddRoad("Gate", "Office", 2);13AddRoad("Store", "Yard", 3);14AddRoad("Office", "Yard", 5);15 16foreach (var (place, list) in roads)17    Console.WriteLine($"{place}: {string.Join(", ", list.Select(r => $"{r.To} ({r.Minutes})"))}");18 19Console.WriteLine($"Degree of Yard: {roads["Yard"].Count}");

Gate: Store (4), Office (2)
Store: Gate (4), Yard (3)
Office: Gate (2), Yard (5)
Yard: Store (3), Office (5)
Degree of Yard: 2

Algorithms usually number the vertices 0 to V − 1 and use an array of lists, which is faster than a dictionary of strings. Keep a separate string[] names if you need the labels back.

Adjacency matrix: a V × V table

m[i, j] holds 1 (or the weight) if there is an edge from i to j. Checking one particular connection is O(1), but the table always uses V² cells, even when there are few edges, and listing the neighbours of a vertex means scanning a whole row.

1int n = 5;2int[][] edges = { new[] { 0, 1 }, new[] { 0, 2 }, new[] { 1, 3 }, new[] { 2, 3 }, new[] { 3, 4 } };3 4var adj = new List<int>[n];                     // adjacency list5for (int i = 0; i < n; i++) adj[i] = new List<int>();6var matrix = new bool[n, n];                    // adjacency matrix7 8foreach (var e in edges)9{10    adj[e[0]].Add(e[1]); adj[e[1]].Add(e[0]);11    matrix[e[0], e[1]] = matrix[e[1], e[0]] = true;12}13 14for (int i = 0; i < n; i++)15    Console.WriteLine($"{i}: {string.Join(" ", adj[i])}");16Console.WriteLine(matrix[3, 4]);                // is there an edge 3-4? O(1)17Console.WriteLine(matrix[0, 4]);

0: 1 2
1: 0 3
2: 0 3
3: 1 2 4
4: 3
True
False

Graphs you never build

Sometimes the graph is implicit: you compute the neighbours when you need them. A grid is a graph where each cell’s neighbours are the cells above, below, left and right. A puzzle is a graph where each state’s neighbours are the states one move away. You will see this in the BFS lesson.

1var deps = new (string Before, string After)[]2{3    ("Survey", "Excavate"), ("Excavate", "Footings"), ("Order steel", "Fabricate"),4    ("Fabricate", "Columns"), ("Footings", "Columns")5};6 7var inDegree = new Dictionary<string, int>();8foreach (var (a, b) in deps)9{10    inDegree.TryAdd(a, 0);11    inDegree[b] = inDegree.GetValueOrDefault(b) + 1;12}13 14foreach (var (task, d) in inDegree)15    Console.WriteLine($"{task}: {d}");16 17var starts = inDegree.Where(p => p.Value == 0).Select(p => p.Key);18Console.WriteLine("Can start now: " + string.Join(", ", starts));

Survey: 0
Excavate: 1
Footings: 1
Order steel: 0
Fabricate: 1
Columns: 2
Can start now: Survey, Order steel