广度优先搜索思想

图的广度优先搜索（Broad First Search）
类似于一个分层搜索的过层，广度优先遍历需要使用一个队列以保持访问的结点的顺序，以便于按这个顺序来访问这些节点的邻接节点。

广度优先吧遍历算法的步骤

  1. 访问初始节点v并标记节点v为已访问
  2. 节点v入队列
  3. 当队列非空时，继续执行，否则算法结束（对v这个节点算法结束）
  4. 出队列，取得队头节点u
  5. 查找节点u的第一个邻接节点w
  6. 若节点u的邻接节点w不存在，则转到步骤3；否则循环执行以下三个步骤：
    1. 若节点w尚未被访问，则访问节点w并标记为已访问
    2. 节点w入队列
    3. 查找节点u的继w邻接节点后的下一个邻接节点w，转到步骤6

      代码

      ```csharp using System; using System.Collections.Generic; using System.Text;

namespace ConsoleApp1 { public class Graph { public List vertexList;//存储顶点集合 public int[,] edges;//存储图对应的邻接矩阵 public int numOfEdges;//表示边的数目 public bool[] isVisited;//存放顶点是否被访问

  1.     public Graph(int n)//n顶点的个数
  2.     {
  3.         //初始化矩阵和vertexList
  4.         edges = new int[n, n];
  5.         vertexList = new List<string>(n);
  6.         isVisited = new bool[n];
  7.     }
  8.     //插入顶点
  9.     public void insertVertex(string vertex)
  10.     {
  11.         vertexList.Add(vertex);
  12.     }
  14.     /// <summary>
  15.     /// 添加边
  16.     /// </summary>
  17.     /// <param name="v1">第一个顶点的下标</param>
  18.     /// <param name="v2">第二个顶点的下标</param>
  19.     /// <param name="weight">权值</param>
  20.     public void insertEdge(int v1,int v2,int weight)
  21.     {
  22.         //因为是无向表，所以v1-v2和v2-v1都需要标记
  23.         edges[v1, v2] = weight;
  24.         edges[v2, v1] = weight;
  25.         numOfEdges++;//两点之间只有一条边
  26.     }
  28.     //显示图对应的矩阵
  29.     public void showGraph()
  30.     {
  31.         for(int i = 0; i < edges.GetLength(0); i++)
  32.         {
  33.             for(int t = 0; t < edges.GetLength(1); t++)
  34.             {
  35.                 Console.Write(edges[i,t]+" ");
  36.             }
  37.             Console.WriteLine();
  38.         }
  39.     }
  42.     #region 广度优先搜索
  43.     //得到第一个邻接节点的下标w
  44.     public int getFirstNeighbor(int index)
  45.     {
  46.         for (int j = 0; j < vertexList.Count; j++)
  47.         {
  48.             if (edges[index, j] > 0)
  49.                 return j;
  50.         }
  51.         return -1;
  52.     }
  53.     //根据前一个邻接节点的下标，来获取下一个邻接节点
  54.     public int getNextNeighbor(int v1, int v2)
  55.     {
  56.         for (int j = v2 + 1; j < vertexList.Count; j++)
  57.         {
  58.             if (edges[v1, j] > 0)
  59.                 return j;
  60.         }
  61.         return -1;
  62.     }
  63.     public void BFS(bool[] isVisited,int i)
  64.     {
  65.         int u;//队列头结点对应的下标
  66.         int w;//邻接节点w
  67.         //队列，记录节点访问的顺序
  68.         Queue<int> queue = new Queue<int>();
  69.         //访问节点，输出信息
  70.         Console.Write(vertexList[i]+"->");
  71.         //标记为已访问
  72.         isVisited[i] = true;
  73.         //将节点加入队列
  74.         queue.Enqueue(i);
  75.         while (queue.Count > 0)
  76.         {
  77.             //取出队列的头结点
  78.             u = queue.Dequeue();
  79.             //得到第一个
  80.             w = getFirstNeighbor(u);
  81.             while (w != -1)//只要不等于-1就是找到了
  82.             {
  83.                 if(!isVisited[w])//没访问过
  84.                 {
  85.                     Console.Write(vertexList[w] + "->");
  86.                     //标记为已经访问
  87.                     isVisited[w] = true;
  88.                     //入队列
  89.                     queue.Enqueue(w);
  90.                 }
  91.                 //已经访问过了，以u的前驱点找w的后一个邻接点
  92.                 w = getNextNeighbor(u, w);//广度优先
  94.             }
  95.         }
  96.     }
  98.     //遍历所有的节点,进行广度优先算法
  99.     public void BFS()
  100.     {
  101.         for(int i = 0; i < vertexList.Count; i++)
  102.         {
  103.             if (!isVisited[i])
  104.                 BFS(isVisited, i);
  105.         }
  106.     }
  107.     #endregion
  108. }

}

```