C#，图论与图算法，有向图（Direct Graph）广度优先遍历（BFS，Breadth First Search）算法与源程序

1 图的广度优先遍历

图的广度优先遍历（或搜索）类似于树的广度优先遍历（参见本文的方法2）。这里唯一需要注意的是，与树不同，图可能包含循环，因此我们可能再次来到同一个节点。为了避免多次处理节点，我们使用布尔访问数组。为简单起见，假设所有顶点都可以从起始顶点到达。

例如，在下图中，我们从顶点2开始遍历。当我们到达顶点0时，我们会查找它的所有相邻顶点。2也是0的相邻顶点。如果我们不标记访问的顶点，那么2将再次处理，它将成为一个非终止过程。下图的宽度优先遍历为2、0、3、1。

2 BFS 的应用

我们前面讨论了图的广度优先遍历算法。我们还讨论了深度优先遍历的应用。本文讨论了广度优先搜索的应用。

1） 无权图的最短路径与最小生成树在无权图中，最短路径是边数最少的路径。对于宽度优先，我们总是使用最小边数从给定源到达顶点。此外，对于无权图，任何生成树都是最小生成树，我们可以使用深度优先遍历或宽度优先遍历来查找生成树。

2） 对等网络。在像BitTorrent这样的对等网络中，广度优先搜索用于查找所有邻居节点。

3） 搜索引擎中的爬虫：爬虫使用广度优先构建索引。这个想法是从源页面开始，跟踪源页面的所有链接，并继续