大多数 C# 题解存图的方式，正是它们超时的原因。接着讲广度优先搜索、不靠调用栈的深度优先搜索，以及顺带就能检测环的拓扑排序。
用 C# 做图论题，有一种特有的失败方式，而且在任何算法运行之前就已经发生了：问题出在图的存储方式上。
下面每个程序都是完整的，都在 .NET 10 上运行过，输出直接从运行结果粘贴而来。
模式 31 — 图怎么存
大多数 C# 题解用的是 List<List<int>>。它好读，也正确。但它会给每个节点分配一个 List 对象，每个对象各有一个底层数组，散落在堆上。20 万个节点就要分配 20 万个对象，每查一次邻居，都要顺着指针跳到内存里的另一个地方。
另一种做法是压缩稀疏行（compressed sparse row，CSR）：整张图放进两个扁平数组。
head 的构造方法是先统计每个节点的度，再求前缀和，和第 3 篇是同一个技巧。结果是一个扁平的邻居数组，加上一个索引数组，标出每个节点的邻居从哪里开始。
int n = 5;
(int u, int v)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)];
// The version most C# solutions use: n List objects, each with its own array.
List<List<int>> adj = [];
for (int i = 0; i < n; i++) adj.Add([]);
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }
Console.WriteLine("List<List<int>>:");
for (int i = 0; i < n; i++) Console.WriteLine($" {i}: [{string.Join(", ", adj[i])}]");
Console.WriteLine($" objects allocated: 1 outer list + {n} inner lists + their backing arrays");
// Compressed sparse row: two arrays, total, for the whole graph.
int[] head = new int[n + 1];
foreach (var (u, v) in edges) { head[u + 1]++; head[v + 1]++; } // degree, offset by one
for (int i = 0; i < n; i++) head[i + 1] += head[i]; // prefix sum -> start offsets
int[] next = new int[edges.Length * 2];
int[] cursor = (int[])head.Clone();
foreach (var (u, v) in edges)
{
next[cursor[u]++] = v;
next[cursor[v]++] = u;
}
Console.WriteLine($"\nCSR:");
Console.WriteLine($" head = [{string.Join(", ", head)}]");
Console.WriteLine($" next = [{string.Join(", ", next)}]");
Console.WriteLine($" objects allocated: 2 arrays, whatever the size of the graph");
Console.WriteLine("\nneighbours of each node, read from CSR:");
for (int u = 0; u < n; u++)
{
var nb = new List<int>();
for (int e = head[u]; e < head[u + 1]; e++) nb.Add(next[e]);
Console.WriteLine($" {u}: [{string.Join(", ", nb)}] (same: {nb.OrderBy(x => x).SequenceEqual(adj[u].OrderBy(x => x))})");
}输出：
List<List<int>>:
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]
objects allocated: 1 outer list + 5 inner lists + their backing arrays
CSR:
head = [0, 2, 4, 6, 9, 10]
next = [1, 2, 0, 3, 0, 3, 1, 2, 4, 3]
objects allocated: 2 arrays, whatever the size of the graph
neighbours of each node, read from CSR:
0: [1, 2] (same: True)
1: [0, 3] (same: True)
2: [0, 3] (same: True)
3: [1, 2, 4] (same: True)
4: [3] (same: True)看 head 是怎么构造的。先把每个节点的度计到 head[u+1] 上，再求前缀和。这和第 3 篇是同一个技巧，这里用来把度转换成起始偏移量。cursor 是一份副本，填充时逐步消耗，这样每个节点的邻居都按顺序写入。
u 的邻居是 next[head[u] .. head[u+1] - 1]。head 有 n+1 格，所以对最后一个节点来说，head[u+1] 也一定存在。这和前缀和数组防差一错误的讲究是一样的。
值得这么做吗？5 个节点的图不值得，代码要给别人读的时候也不值得。当 n 到了几十万，就值得了：通过和不通过，差的就是这一点。
适用场景：图很大，而且是静态的。如果边是边读边加的，还是用列表。
模式 32 — 用 BFS 求最短路径
在无权图上，广度优先搜索（BFS）就能求出最短路径，而且全程不需要比较两个距离。
原因在队列。队列会先装下完整的一层，然后才装下一层的节点。所以一个节点第一次被访问到时，走的就是最短路径，之后不可能再找到更短的。
队列装完一整层，才会装下一层的节点，所以节点第一次被访问到时，走的就是最短路径。这就是 BFS 不需要比较距离的原因。第 8 篇的 Dijkstra 则不同：边有权重，后来的路径可能更短。
int n = 7;
(int, int)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 6)];
List<int>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }
int start = 0, goal = 5;
int[] dist = new int[n];
int[] parent = new int[n];
Array.Fill(dist, -1);
Array.Fill(parent, -1);
Queue<int> q = [];
q.Enqueue(start);
dist[start] = 0;
while (q.Count > 0)
{
int u = q.Dequeue();
Console.WriteLine($"visit {u} (distance {dist[u]})");
foreach (int v in adj[u])
{
if (dist[v] != -1) continue; // already has its shortest distance
dist[v] = dist[u] + 1;
parent[v] = u;
q.Enqueue(v);
Console.WriteLine($" -> {v} first reached, distance {dist[v]}");
}
}
List<int> path = [];
for (int at = goal; at != -1; at = parent[at]) path.Add(at);
path.Reverse();
Console.WriteLine($"\ndistances: [{string.Join(", ", dist)}]");
Console.WriteLine($"path {start} -> {goal}: {string.Join(" -> ", path)} (length {dist[goal]})");输出：
visit 0 (distance 0)
-> 1 first reached, distance 1
-> 2 first reached, distance 1
visit 1 (distance 1)
-> 3 first reached, distance 2
visit 2 (distance 1)
-> 6 first reached, distance 2
visit 3 (distance 2)
-> 4 first reached, distance 3
visit 6 (distance 2)
visit 4 (distance 3)
-> 5 first reached, distance 4
visit 5 (distance 4)
distances: [0, 1, 1, 2, 3, 4, 2]
path 0 -> 5: 0 -> 1 -> 3 -> 4 -> 5 (length 4)关键是 if (dist[v] != -1) continue; 这一行，再加上在入队时就设置 dist[v]，而不是出队时。如果出队时才标记，一个节点在被处理之前可能被好几个邻居推入队列，在队列里出现多次，队列会膨胀到 O(边数)。
parent 只多花一个数组，换来的是实际路线，而不仅是长度。从终点往回走，再反转即可。问距离的题，大多最后都会问路径。
代价：时间和空间都是 O(V + E)。
适用场景：边没有权重，或者权重全都相同。如果权重不同，这个方法会给出错误答案，你需要的是第 8 篇。
模式 33 — 不用调用栈的 DFS
递归写的深度优先搜索（DFS）更短，也更好读。但它运行在一个线程上，而这个线程的栈默认只有 1MB，一条 10 万个节点的路径就能把它耗尽。
这一点在 C# 里比在某些语言里更要紧，因为 StackOverflowException 无法捕获。运行时会直接终止进程。没有异常处理，没有能据以处理的错误信息，只有一个死掉的进程和一个判题结果。
有两种解决办法：改用显式栈，或者给递归单独一个更大的栈。
using System.Threading;
int n = 7;
(int, int)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 6)];
List<int>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }
// Explicit stack. Same traversal, no call frames.
bool[] seen = new bool[n];
Stack<int> st = [];
List<int> order = [];
st.Push(0);
while (st.Count > 0)
{
int u = st.Pop();
if (seen[u]) continue; // a node can be pushed several times before it is popped
seen[u] = true;
order.Add(u);
// Pushed in reverse so the smallest neighbour is popped first.
for (int i = adj[u].Count - 1; i >= 0; i--)
if (!seen[adj[u][i]]) st.Push(adj[u][i]);
}
Console.WriteLine($"iterative DFS order: {string.Join(" -> ", order)}");
// How deep can recursion go? On the default 1MB main-thread stack, not very.
// A StackOverflowException cannot be caught in .NET — the process just dies —
// so the fix is to give the recursion its own thread with a bigger stack.
int depth = 0;
void Deep(int k) { if (k == 0) return; depth++; Deep(k - 1); }
var t = new Thread(() => Deep(500_000), 256 * 1024 * 1024);
t.Start();
t.Join();
Console.WriteLine($"recursion on a 256MB stack: reached depth {depth:N0}, no crash");输出：
iterative DFS order: 0 -> 1 -> 3 -> 2 -> 6 -> 4 -> 5
recursion on a 256MB stack: reached depth 500,000, no crash显式栈的版本有一个细节：出栈后要 if (seen[u]) continue;。一个节点在出栈之前，可能被好几个邻居压入，所以同一个下标出现在栈里不止一次是正常的，后面几次必须跳过。邻居倒序压栈，遍历顺序就和递归版本一致。
开线程是另一条路，很多用 C# 打竞赛的代码就是这么写的。new Thread(action, 256 * 1024 * 1024) 给递归四分之一 GB 的栈，上面的输出显示 50 万层调用毫无问题。这样能保留递归写法，对树形 DP 来说是实实在在的好处。
适用场景：图很深，比如一条链、一棵退化的树、沿长边方向遍历的网格。如果深度可能超过几万，就别在主线程上用递归。
模式 34 — Flood fill
网格上的连通分量：数岛屿。
string[] grid =
[
"11000",
"11000",
"00100",
"00011",
];
int rows = grid.Length, cols = grid[0].Length;
bool[,] seen = new bool[rows, cols];
int islands = 0;
int[] dr = [-1, 1, 0, 0];
int[] dc = [0, 0, -1, 1];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
{
if (grid[r][c] != '1' || seen[r, c]) continue;
islands++;
List<(int, int)> cells = [];
Queue<(int r, int c)> q = [];
q.Enqueue((r, c));
seen[r, c] = true;
while (q.Count > 0)
{
var (cr, cc) = q.Dequeue();
cells.Add((cr, cc));
for (int d = 0; d < 4; d++)
{
int nr = cr + dr[d], nc = cc + dc[d];
// One bounds check, and mark on ENQUEUE not on dequeue.
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (grid[nr][nc] != '1' || seen[nr, nc]) continue;
seen[nr, nc] = true;
q.Enqueue((nr, nc));
}
}
Console.WriteLine($"island {islands}: {cells.Count} cells {string.Join(" ", cells.Select(x => $"({x.Item1},{x.Item2})"))}");
}
Console.WriteLine($"\nislands: {islands}");输出：
island 1: 4 cells (0,0) (1,0) (0,1) (1,1)
island 2: 1 cells (2,2)
island 3: 2 cells (3,3) (3,4)
islands: 3网格就是图，唯一的区别是邻居靠计算得出，而不是存下来的。dr/dc 数组让这部分只用一个循环，而不是复制四段代码；要加上对角线方向，也只需再加四个元素，而不是再写四段。
有两个习惯值得保留。第一，在读取网格之前检查边界，而且放在同一个判断里。C# 的 || 从左到右求值，正是这个顺序保证了下标不会越界。第二，seen 在入队时设置，理由和模式 32 完全一样。
这里用 BFS 而不是 DFS，正是因为一大片相连的格子恰好就是模式 33 里的深递归情况。一个全是 1 的 500×500 网格是一个连通分量，深度可达 25 万格。
代价：O(rows × cols)。
适用场景：题目是网格，比如岛屿、区域、填色、随时间扩散。
模式 35 — 拓扑排序，顺带检测环
给节点排序，使每条边都指向前方。任务调度、构建依赖、课程先修关系都是这类问题。
Kahn 算法：统计每个节点有多少条边指向它，从没有边指向的节点开始，每移除一个节点，就把它指向的节点的计数减一。
如果队列空了，还有节点没输出，那么剩下的节点都仍有边指向它们。能让这种情况持续下去的，只有环。环检测不是额外的一轮遍历，而是最后的那个计数。
int n = 6;
// A directed graph: an edge u -> v means u must come before v.
(int u, int v)[] edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)];
static List<int>? TopoSort(int n, (int u, int v)[] edges)
{
List<int>[] outs = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
int[] indeg = new int[n];
foreach (var (u, v) in edges) { outs[u].Add(v); indeg[v]++; }
// Everything with nothing pointing at it can go first.
Queue<int> ready = new(Enumerable.Range(0, n).Where(i => indeg[i] == 0));
List<int> order = [];
while (ready.Count > 0)
{
int u = ready.Dequeue();
order.Add(u);
foreach (int v in outs[u])
if (--indeg[v] == 0) ready.Enqueue(v);
}
// Anything left has a cycle behind it: its in-degree never reached zero.
return order.Count == n ? order : null;
}
Console.WriteLine($"in-degrees start: {string.Join(", ", Enumerable.Range(0, n).Select(i => $"{i}:{edges.Count(e => e.v == i)}"))}");
var order = TopoSort(n, edges);
Console.WriteLine($"order: {(order is null ? "IMPOSSIBLE" : string.Join(" -> ", order))}");
// Every edge must point forwards in the result.
int[] pos = new int[n];
for (int i = 0; i < order!.Count; i++) pos[order[i]] = i;
Console.WriteLine($"every edge points forwards: {edges.All(e => pos[e.u] < pos[e.v])}");
Console.WriteLine();
(int u, int v)[] cyclic = [(0, 1), (1, 2), (2, 0)];
Console.WriteLine($"with a cycle 0->1->2->0: {(TopoSort(3, cyclic) is null ? "IMPOSSIBLE — detected" : "sorted?!")}");输出：
in-degrees start: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0
order: 4 -> 5 -> 2 -> 0 -> 3 -> 1
every edge points forwards: True
with a cycle 0->1->2->0: IMPOSSIBLE — detected值得注意的是环检测，因为它不需要单独再遍历一遍。如果队列在 n 个节点全部输出之前就空了，剩下的节点仍有边指向它们。环外的节点不可能指向所有这些节点，所以一定有环。order.Count == n 就是全部的检查。
最后那行验证，是做任何排序类题目的好习惯：建一个位置查找表，断言每条边都指向前方。拓扑序通常不唯一，拿一个预期答案去比对是错误的测试方式。
代价：O(V + E)。
适用场景：题目描述的是依赖、先修条件或顺序约束；以及任何需要判断有向图里到底有没有环的时候。
要点
List<List<int>>每个节点分配一个对象。小图没问题；到了 10⁵ 个节点，CSR 整张图只要两个数组，邻居在内存里是连续的。head是对度求前缀和得到的，有n+1格，这样最后一个节点的结束偏移量也存在。- BFS 能求最短路径，全靠分层。不需要比较距离，而边一旦有权重，失效的正是这一点。
- 节点在入队时标记，绝不要在出队时标记。否则同一个节点会多次入队。
- .NET 里无法捕获
StackOverflowException。深递归不会抛出异常，而是直接杀死进程。用显式栈，或者开一个大栈的线程。 - 同一个节点在显式栈里出现两次是正常的。出栈后要检查
seen，不能只在压栈前检查。 order.Count == n就是环检测。不需要更多，也不能更少。
第 8 篇加入权重，BFS 在那里就不再正确：用 PriorityQueue 实现的 Dijkstra，堆纯属多余的 0-1 情况，以及并查集。