C#深度优先搜索（DFS）遍历图详解（小白也能学会的图遍历算法入门教程）

什么是深度优先搜索（DFS）？

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索树或图的算法。它的核心思想是：从一个起始节点出发，沿着一条路径尽可能深入地访问节点，直到无法继续为止，然后回溯并尝试其他路径。

DFS 常用于：

• 检测图中是否存在环
• 寻找连通分量
• 拓扑排序
• 解决迷宫问题

C# 中如何表示图？

在 C# 中，图通常可以用邻接表（Adjacency List）来表示。邻接表使用字典（Dictionary<T, List<T>>）或列表数组来存储每个节点及其相邻节点。

例如，以下是一个简单的无向图：

0 —— 1 —— 2|         |3 —— 4 —— 5

这个图可以用如下邻接表表示：

C# 实现 DFS 图遍历

下面是一个完整的 C# 示例，演示如何使用递归方式实现 DFS图遍历：

using System;using System.Collections.Generic;class Graph{    // 使用 Dictionary 表示邻接表    private Dictionary<int, List<int>> adjacencyList;    public Graph()    {        adjacencyList = new Dictionary<int, List<int>>();    }    // 添加边（无向图）    public void AddEdge(int u, int v)    {        if (!adjacencyList.ContainsKey(u))            adjacencyList[u] = new List<int>();        if (!adjacencyList.ContainsKey(v))            adjacencyList[v] = new List<int>();        adjacencyList[u].Add(v);        adjacencyList[v].Add(u);    }    // 深度优先搜索（递归实现）    public void DFS(int startVertex)    {        HashSet<int> visited = new HashSet<int>();        DFSUtil(startVertex, visited);    }    private void DFSUtil(int vertex, HashSet<int> visited)    {        // 标记当前节点为已访问        visited.Add(vertex);        Console.Write(vertex + " ");        // 遍历所有邻接节点        if (adjacencyList.ContainsKey(vertex))        {            foreach (int neighbor in adjacencyList[vertex])            {                if (!visited.Contains(neighbor))                {                    DFSUtil(neighbor, visited);                }            }        }    }}// 测试代码class Program{    static void Main()    {        Graph g = new Graph();        g.AddEdge(0, 1);        g.AddEdge(0, 3);        g.AddEdge(1, 2);        g.AddEdge(2, 5);        g.AddEdge(3, 4);        g.AddEdge(4, 5);        Console.WriteLine("深度优先遍历结果（从节点 0 开始）：");        g.DFS(0);        // 输出可能为：0 1 2 5 4 3    }}

代码解析

• Graph 类：封装了图的数据结构和 DFS 方法。
• AddEdge 方法：用于添加无向图的边，自动维护邻接表。
• DFS 方法：入口函数，初始化已访问集合并调用递归辅助函数。
• DFSUtil 方法：真正的递归 DFS 实现，访问当前节点后，递归访问所有未访问的邻居。

运行上述代码，你将看到类似 0 1 2 5 4 3 的输出（具体顺序可能因图结构不同而略有差异），这就是 C#图算法中 DFS 的典型遍历路径。

DFS 的时间与空间复杂度

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。因为每个节点和每条边最多被访问一次。
• 空间复杂度：O(V)，主要用于存储 visited 集合和递归调用栈。

总结

通过本教程，你已经掌握了如何在 C# 中实现 深度优先遍历教程的核心逻辑。DFS 不仅是面试常考算法，也是解决实际问题的有力工具。建议你动手敲一遍代码，修改图的结构，观察不同起点的遍历结果，加深理解。

记住，学习 C#深度优先搜索的关键在于理解“深入到底再回溯”的思想。多练习，你很快就能熟练运用它！