当前位置：首页 > article >正文

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

article 2025/1/14 1:44:58

1 图的广度优先遍历

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

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

2 BFS 的应用

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

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

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

3）搜索引擎中的爬虫：爬虫使用广度优先构建索引。这个想法是从源页面开始，跟踪源页面的所有链接，并继续这样做。深度优先遍历也可用于爬虫，但宽度优先遍历的优点是，构建树的深度或级别可能会受到限制。

4）社交网站：在社交网络中，我们可以使用广度优先搜索到“k”级，在给定的距离“k”内找到与某人保持距离的人。

播放视频

5） GPS导航系统：广度优先搜索用于查找所有相邻位置。

6）网络广播：在网络中，广播的数据包遵循广度优先搜索到达所有节点。

7）在垃圾收集中：宽度优先搜索用于使用切尼算法复制垃圾收集。有关详细信息，请参阅和。广度优先搜索优于深度优先搜索，因为参考位置更好：

8）无向图中的循环检测：在无向图中，可以使用广度优先搜索或深度优先搜索来检测循环。我们也可以使用BFS来检测有向图中的循环，

9） Ford–Fulkerson算法在Ford-Fulkerson算法中，我们可以使用宽度优先或深度优先遍历来找到最大流。广度优先遍历是首选，因为它将最坏情况的时间复杂度降低到O（VE2）。

10）为了测试图是否是二部图，我们可以使用广度优先遍历或深度优先遍历。

11）路径查找我们可以使用宽度优先或深度优先遍历来查找两个顶点之间是否存在路径。

12）查找一个连接组件中的所有节点：我们可以使用广度优先或深度优先遍历来查找从给定节点可以访问的所有节点。

许多算法，如Prim的最小生成树和Dijkstra的单源最短路径，都使用类似于广度优先搜索的结构。

由于广度优先搜索是图的核心算法之一，因此可以有更多的应用。

参考：

C#，图（Graph）的数据结构设计与源代码https://blog.csdn.net/beijinghorn/article/details/125133711?spm=1001.2014.3001.5501

3 BFS源代码

using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		public List<int> Traversal { get; set; } = new List<int>();
		
		public void BFS_For_Direct_Graph(int s)
		{
			bool[] visited = new bool[Node_Number];
			for (int i = 0; i < Node_Number; i++)
			{
				visited[i] = false;
			}
			List<int> queue = new List<int>();

			visited[s] = true;
			queue.Add(s);

			while(queue.Count >0)
			{
				s = queue[0];

				Traversal.Add(s);
				queue.RemoveAt(0);

				List<int> list = Adjacency[s];

				foreach (var val in list)
				{
					if (visited[val] == false)
					{
						visited[val] = true;
						queue.Add(val);
					}
				}
			}
		}
	}

	public static partial class GraphDrives
	{
		public static string BFS_For_Direct_Graph()
		{
			Graph g = new Graph(8, 0, true);

			g.AddEdge(0, 1);
			g.AddEdge(0, 2);
			g.AddEdge(1, 2);
			g.AddEdge(2, 0);
			g.AddEdge(2, 3);
			g.AddEdge(3, 3);

			g.AddEdge(1, 4);
			g.AddEdge(1, 5);

			g.AddEdge(4, 6);
			g.AddEdge(4, 7);

			g.BFS_For_Direct_Graph(2);

			return String.Join(",", g.Traversal.ToArray());
		}
	}
}

查看全文

http://www.kler.cn/a/501531.html