C#图表算法之无向图

什么是无向图

无向图是图的一种，其中边没有方向。也就是说，图中的节点之间的关系是没有顺序的，就像两个人之间的友谊关系不分先后。

在 C# 中，我们可以使用 Dictionary<T1, List<T2>> 来表示一个无向图。其中 T1 表示节点，T2 表示节点和它相邻的节点组成的列表。

构建无向图

下面是一个构建无向图的代码示例。

public Dictionary<int, List<int>> BuildGraph(int[][] edges)
{
    var graph = new Dictionary<int, List<int>>();
    foreach (var edge in edges)
    {
        var v1 = edge[0];
        var v2 = edge[1];
        if (!graph.ContainsKey(v1)) graph[v1] = new List<int>();
        if (!graph.ContainsKey(v2)) graph[v2] = new List<int>();
        graph[v1].Add(v2);
        graph[v2].Add(v1);
    }
    return graph;
}

这个方法接收一个 int[][] 数组作为参数，并返回一个 Dictionary<int, List<int>> 类型的无向图。数组中的每个元素表示节点之间的关系。

例如，[[0,1],[1,2],[2,0]] 表示 0 和 1 相连，1 和 2 相连，2 和 0 相连。使用 BuildGraph 方法传入这个数组可以得到如下结果：

{
    0: [1, 2],
    1: [0, 2],
    2: [1, 0]
}

遍历无向图

有两种方式可以遍历无向图：深度优先搜索（DFS）和广度优先搜索（BFS）。

DFS

深度优先搜索是一种递归算法，它从起始节点开始，在遍历到一个新节点时递归调用自己，直到达到某个结束条件。在遍历过程中，每个节点都会被标记为已访问。

下面是一个使用 DFS 遍历无向图的示例。

public void DFS(Dictionary<int, List<int>> graph, int vertex, HashSet<int> visited)
{
    visited.Add(vertex);
    Console.WriteLine(vertex);
    foreach (var neighbor in graph[vertex])
    {
        if (!visited.Contains(neighbor))
        {
            DFS(graph, neighbor, visited);   
        }
    }
}

这个方法接收一个无向图、起始节点和一个已访问节点列表作为参数。方法中会先标记起始节点为已访问，然后输出当前节点。接着遍历起始节点的所有相邻节点，如果某个相邻节点尚未被访问过，则递归调用 DFS 方法。

例如，假设现在有如下无向图：

{
    0: [1, 2],
    1: [0, 2],
    2: [1, 0]
}

如果我们从节点 0 开始执行 DFS，则程序的输出为：

0
1
2

BFS

广度优先搜索是一种迭代算法，它从起始节点开始，先遍历起始节点的所有相邻节点，然后逐层遍历每个相邻节点的相邻节点。

下面是一个使用 BFS 遍历无向图的示例。

public void BFS(Dictionary<int, List<int>> graph, int start)
{
    var queue = new Queue<int>();
    var visited = new HashSet<int>();

    queue.Enqueue(start);
    visited.Add(start);

    while (queue.Count > 0)
    {
        var vertex = queue.Dequeue();
        Console.WriteLine(vertex);

        foreach (var neighbor in graph[vertex])
        {
            if (!visited.Contains(neighbor))
            {
                queue.Enqueue(neighbor);
                visited.Add(neighbor);
            }
        }
    }
}

这个方法接收一个无向图和起始节点作为参数。方法中会创建一个队列和一个已访问节点列表。起始节点会被加入队列和已访问节点列表。然后程序进入一个循环，每次从队列中取出一个节点并输出。接着遍历当前节点的所有相邻节点，如果某个相邻节点尚未被访问过，则将其加入队列和已访问节点列表。

例如，假设现在有如下无向图：

{
    0: [1, 2],
    1: [0, 2],
    2: [1, 0]
}

如果我们从节点 0 开始执行 BFS，则程序的输出为：

0
1
2

示例说明

示例一

假设现在有如下无向图：

{
    0: [1, 2],
    1: [0, 2],
    2: [1, 0]
}

如果我们使用 DFS 从节点 1 开始遍历，程序的输出为：

1
0
2

如果我们使用 BFS 从节点 1 开始遍历，程序的输出为：

1
0
2

示例二

假设现在有如下无向图：

{
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1, 4],
    4: [3]
}

如果我们使用 DFS 从节点 0 开始遍历，程序的输出为：

0
1
2
3
4

如果我们使用 BFS 从节点 0 开始遍历，程序的输出为：

0
1
2
3
4

总结

本文介绍了如何使用 C# 构建无向图，并通过深度优先搜索和广度优先搜索遍历了无向图。无向图是图的一种，其中边没有方向，节点之间的关系没有先后顺序。在 C# 中，我们可以使用 Dictionary<T1, List<T2>> 来表示一个无向图。使用 DFS 和 BFS 可以遍历无向图。