深度优先搜索的演示学习法——BlackBlank平台应用教学案例

Posted by Cww97 on 2017-11-08

深度优先搜索的演示学习法——BlackBlank平台应用教学案例

1.DFS简介

深度优先搜索,简称DFS,属于图算法的一种,英文全称为Depth First Search。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,每个节点只能访问一次。##2.深度优先搜索之演示过程下图是一张无向图,亦是一棵二叉树,我们将对它进行DFS遍历。
这里写图片描述
如果你想看动态演示,请点击如下链接:
BlackBlank之DFS
按照如下的顺序遍历:
1.0->1->3->7,此时已到尽头,回溯将成为不二选择。
2.返回到3后遍历到8,又是尽头,继续回溯。
3.回溯到1,以此类推,下面遍历到的节点分别是4,9,10,2,5,6。
4.遍历完毕。

3.深度优先搜索之问题案例

3.1.举例给出如下所示的图,问从图中的标号为0的节点出发,是否存在一条路径长度为4的搜索路径。

这里写图片描述
这里写图片描述

3.2.处理过程

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
即找到一条路径长度为4 的搜索路径。

3.3.对应例子的C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "jsoncppheader.h"
#include <string>
DirectedGraphTracer tracer = DirectedGraphTracer();
LogTracer logger = LogTracer();
int G[11][11] = {
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
void DFS(int node,int parent) {
if(parent != -1) tracer.visit(node, parent).wait();
for (int i = 0; i < 11; i++) {
if (G[node][i]) {
DFS(i, node);
}
}
}
int main()
{
tracer.setTreeData(G[0], 11, 11, 0);
tracer.attach(logger.id);
DFS(0, -1);
}

4.结语

借助BlackBlank网站,我们清晰地为大家演示了DFS算法的过程,展现了她的原貌,展现了递归之美。感兴趣的读者也可以点击进入http://www.blackblank.cn/大显身手,让数据结构和算法在你的屏幕上跃然起舞。