C#，图论与图算法，图（Graph）广度优先遍历（BFS，Breadth First Search）算法与源代码

深度优先算法（DFS，Deep First Search）与 宽度优先遍历（BFS，Breadth First Search） 是树、图数据结构的基础性、标准性的遍历算法。

深度优先算法（DFS，Deep First Search）

深度优先搜索（DFS）是一种用于搜索图形或树数据结构的算法。该算法从树的根（顶部）节点开始，尽可能沿着给定的分支（路径）向下，然后回溯，直到找到一条未探索的路径，然后进行探索。该算法会一直这样做，直到整个图都被研究完毕。计算机科学中的许多问题都可以用图形来思考。例如，分析网络、映射路由、调度和查找生成树都是图问题。为了分析这些问题，像深度优先搜索这样的图搜索算法很有用。

深度优先搜索通常在其他更复杂的算法中用作子例程。例如，匹配算法Hopcroft–Karp使用DFS作为其算法的一部分，以帮助在图中找到匹配。DFS还用于树遍历算法，也称为树搜索，它在旅行商问题和福特-富尔克森算法中有应用。

广度优先遍历（BFS，Breadth First Search）

广度优先搜索（BFS）从图G的0级顶点X开始。然后我们访问与X相邻的所有顶点。访问后，我们将这些顶点标记为“已访问”，并将其放置到1级。然后我们从1级顶点开始，对每个1级顶点应用相同的方法，以此类推。当访问了图的每个顶点时，BFS遍历终止。

BFS算法

其概念是在访问相邻顶点的其他相邻顶点之前访问所有相邻顶点。

将所有节点的状态初始化为“就绪”。

将源顶点放入队列，并将其状态更改为“等待”。

重复以下两个步骤，直到队列为空−

从队列中删除第一个顶点，并将其标记为“已访问”。

将状态为“就绪”的已移除顶点的所有邻居添加到队列后部。将其状态标记为“等待”。

源程序：

请参考：

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

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

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

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

			while (queue.Any())
			{
				s = queue.First();
				Traversal.Add(s);
				queue.RemoveFirst();

				List<int> list = Adjacency[s];
				foreach (var val in list)
				{
					if (!visited[val])
					{
						visited[val] = true;
						queue.AddLast(val);
					}
				}
			}
		}
	}

	public static partial class GraphDrives
	{
		public static string BFS()
		{
			Graph g = new Graph(4);

			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.BFS(2);

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

POWER BY TRUFFER.CN