图的遍历

2021-03-09

图的遍历思想

图的遍历思想和树的遍历思想是一样的,图的遍历意味着需要将图中每个顶点访问一遍，并且不能有重复的访问

有两种算法可以对图进行遍历

广度优先搜索(Breadth-First Search,简称BFS)
深度优先搜索(Depth-First Search,简称DFS)

两种遍历算法，都需要明确指定第一个被访问的顶点

两种算法的思想：

BFS: 基于队列，入队列的顶点先被探索
DFS: 基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
为了记录顶点是否被访问过，我们使用三种颜色来翻译它们的状态
(1)白色：表示该顶点还没有被访问
(2)灰色：表示该顶点被访问过，但并未被探索完
(3)黑色：表示该顶点被访问过且完全被探索完

广度优先搜索算法的思路：

广度优先搜索会从指定对第一个顶点开始遍历图，先访问器所有的相邻点，就像一次访问图的一层.换句话说，就是先宽后深的访问顶点
广度优先搜索的实现：

创建一个队列Q
将v标注为被发现的(白色),并将v假如到队列Q
如果Q非空,执行下面的步骤:
1. 将v从Q中取出队列
2. 将v标注额为被发现的灰色
3. 将v所有的未被访问过的邻接点(白色),加入到队列中
4. 将v标志位黑色

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save

3、在根目录_config.yml里添加配置：

  jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

勤奋的代码搬运工<br>一位刚出来实习的前端程序员<br>谢谢大家