本文主要是介绍C#,图论与图算法,有向图(Direct Graph)广度优先遍历(BFS,Breadth First Search)算法与源程序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1 图的广度优先遍历
图的广度优先遍历(或搜索)类似于树的广度优先遍历(参见本文的方法2)。这里唯一需要注意的是,与树不同,图可能包含循环,因此我们可能再次来到同一个节点。为了避免多次处理节点,我们使用布尔访问数组。为简单起见,假设所有顶点都可以从起始顶点到达。
例如,在下图中,我们从顶点2开始遍历。当我们到达顶点0时,我们会查找它的所有相邻顶点。2也是0的相邻顶点。如果我们不标记访问的顶点,那么2将再次处理,它将成为一个非终止过程。下图的宽度优先遍历为2、0、3、1。
2 BFS 的应用
我们前面讨论了图的广度优先遍历算法。我们还讨论了深度优先遍历的应用。本文讨论了广度优先搜索的应用。
1) 无权图的最短路径与最小生成树在无权图中,最短路径是边数最少的路径。对于宽度优先,我们总是使用最小边数从给定源到达顶点。此外,对于无权图,任何生成树都是最小生成树,我们可以使用深度优先遍历或宽度优先遍历来查找生成树。
2) 对等网络。在像BitTorrent这样的对等网络中,广度优先搜索用于查找所有邻居节点。
3) 搜索引擎中的爬虫:爬虫使用广度优先构建索引。这个想法是从源页面开始,跟踪源页面的所有链接,并继续
这篇关于C#,图论与图算法,有向图(Direct Graph)广度优先遍历(BFS,Breadth First Search)算法与源程序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!