C#图的广度优先搜索优化（从入门到高效实现BFS算法）

基础版 BFS 实现（C#）

首先，我们用 C# 实现一个最基础的 BFS。这里使用邻接表表示图，并借助 Queue<T> 来管理待访问节点。

using System;using System.Collections.Generic;public class Graph{    private readonly Dictionary<int, List<int>> _adjacencyList;    public Graph()    {        _adjacencyList = new Dictionary<int, List<int>>();    }    public void AddEdge(int from, int to)    {        if (!_adjacencyList.ContainsKey(from))            _adjacencyList[from] = new List<int>();        if (!_adjacencyList.ContainsKey(to))            _adjacencyList[to] = new List<int>();        _adjacencyList[from].Add(to);        // 如果是无向图，还需添加反向边        // _adjacencyList[to].Add(from);    }    public void BFS(int start)    {        var visited = new HashSet<int>();        var queue = new Queue<int>();        queue.Enqueue(start);        visited.Add(start);        while (queue.Count > 0)        {            int current = queue.Dequeue();            Console.WriteLine($"访问节点: {current}");            if (_adjacencyList.TryGetValue(current, out var neighbors))            {                foreach (int neighbor in neighbors)                {                    if (!visited.Contains(neighbor))                    {                        visited.Add(neighbor);                        queue.Enqueue(neighbor);                    }                }            }        }    }}

这段代码清晰展示了 BFS 的基本逻辑。但如果你处理的是大规模图（如百万级节点），这种写法可能存在性能瓶颈。接下来，我们将围绕 C#图算法 和 BFS性能提升 展开优化。

BFS 优化技巧（C# 实践）

1. 使用数组代替 HashSet（适用于连续整数节点）

如果图的节点编号是连续的整数（如 0 到 N-1），使用布尔数组 bool[] visited 比 HashSet<int> 更快，因为数组访问是 O(1) 且无哈希计算开销。

public void OptimizedBFS(int start, int nodeCount){    bool[] visited = new bool[nodeCount];    var queue = new Queue<int>();    queue.Enqueue(start);    visited[start] = true;    while (queue.Count > 0)    {        int current = queue.Dequeue();        Console.WriteLine($"访问节点: {current}");        if (_adjacencyList.TryGetValue(current, out var neighbors))        {            foreach (int neighbor in neighbors)            {                if (!visited[neighbor])                {                    visited[neighbor] = true;                    queue.Enqueue(neighbor);                }            }        }    }}

2. 预分配队列容量

使用 new Queue<int>(capacity) 预设容量，避免频繁扩容带来的内存拷贝开销。

3. 避免重复 TryGetValue 调用

在循环外缓存邻接表引用，减少字典查找次数。

完整优化示例

public void FullyOptimizedBFS(int start, int nodeCount){    bool[] visited = new bool[nodeCount];    var queue = new Queue<int>(nodeCount); // 预分配容量    queue.Enqueue(start);    visited[start] = true;    while (queue.Count > 0)    {        int current = queue.Dequeue();        // Console.WriteLine($"访问节点: {current}"); // 如需输出可保留        // 直接获取邻居列表，避免多次字典查找        if (_adjacencyList.TryGetValue(current, out List<int> neighbors))        {            for (int i = 0; i < neighbors.Count; i++)            {                int neighbor = neighbors[i];                if (!visited[neighbor])                {                    visited[neighbor] = true;                    queue.Enqueue(neighbor);                }            }        }    }}

总结

通过本文，你不仅学会了如何在 C# 中实现基础的 图遍历C# 算法，还掌握了多种 广度优先搜索优化 技巧。记住：优化要基于实际数据特征（如节点是否连续、图规模大小等）。合理运用这些方法，你的 BFS 程序将运行得更快、更高效！

无论是面试准备还是实际项目开发，掌握 C#图算法 和 BFS性能提升 都能让你脱颖而出。快动手试试吧！