目录
到了DFS与BFS这里就是一个省一的分界线了,能搞定的省一基本没有问题,当然,也有靠纯暴力进入省一的,但是几率就会小一些。这篇文章我已经将DFS拆分的很细了呢,希望能帮助大家跨过蓝桥杯的这个分水岭。 如果帮助到了你,请留下你的三连支持。
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。
图中的深度结果就是:0->1->3->4->2
这是深度搜索DFS的遍历方式。
我们已经知道DFS是怎么个逻辑了,那么我们就画一个图做个DFS的搜索。(图随便画,一会自己能根据深度搜索的理论把对应的数组写出来就行)。
这里我们来自己画。画的跟树类似,可以使用类创建左右孩子的方式来解决,但是咱们为了更好的让大一的孩子们理解,所以用一个类来决绝这个问题。
途中我们依照DFS深度搜索的方式目标输出结果是:1->2->4->7->5->3->6。我们接下来就开始我们的编码,看看是否能按照这个DFS的方式进行遍历。
为了帮助孩子们理解,我这里使用的是拼音拼写的变量【dian】
public static String dian[] = { "1", "2", "3", "4", "5", "6", "7" };
我们所有的操作都会依赖于这个长度来进行遍历,故而这里我单独写了一下:
public static int d_length=d.length;
我们用二位数组来表达我们的输出顺序。
1的关联方式是:1列链接1,3故而有数组{0,1,1,0,0,0,0}来表示【1】,那么,同理我们依次推导出2~7的数组表达。
挨个根据图来写,只要有链接就记录一个【1】,没有链接就记录【0】,自身遇到自身记录【0】。
public static int[][] arr= {
{0,1,1,0,0,0,0},
{1,0,0,1,1,0,0},
{1,0,0,0,0,1,0},
{0,1,0,0,0,0,1},
{0,1,0,0,0,0,0},
{0,0,1,0,0,0,0},
{0,0,0,1,0,0,0},
};
这样我们就把图形的规律记录成了一个长度为定点长度的二位数组。
public static boolean[] isfStatus;
这里我们共计创建了4个全局变量,依次是:
顶点、图转换数组、判断是否走过、记录每一个节点的遍历过程,走过则记录为true。
/**
* 顶点
*/
public static String d[] = { "1", "2", "3", "4", "5", "6", "7"
/**
* 图转换数组
*/
public static int[][] arr= {
{0,1,1,0,0,0,0},
{1,0,0,1,1,0,0},
{1,0,0,0,0,1,0},
{0,1,0,0,0,0,1},
{0,1,0,0,0,0,0},
{0,0,1,0,0,0,0},
{0,0,0,1,0,0,0},
};
/**
* 顶点长度
*/
public static int d_length=d.length;
/**
* 记录每一个节点的遍历过程,走过则记录为true
*/
public static boolean[] isfStatus;
这里我们所需要的变量就准备好了。
我们这里其实是注意行的深入,故而只要false就代表没有走过,我们需要遍历一下图,看看是否有对应的链接数组。
/**
* 开始DFS
*/
public static void DFSStart() {
//初始化数组,记录使用过程
isfStatus = new boolean[d_length];
//遍历图数组
for (int i = 0; i < d_length; i++) {
//因为初始的布尔数组都是false,所以只要是false就是没有走过
if (isfStatus[i] == false) {
//进度到深度搜索的递归
DFS(i);
}
}
}
我们这里需要注意的是深度搜索的节点遍历范围,我们从第一个开始,然后逐一遍历。
/**
* 递归深搜
* @param i
*/
private static void DFS(int i) {
// TODO Auto-generated method stub
System.out.print(d[i] + " ");
isfStatus[i] = true;
// 深度搜索子节点·从第一个节点到下一个节点
for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) {
if (!isfStatus[j]) {
DFS(j);
}
}
}
这里能看到我写了两个判断,判断1是arr[i][j]>0,还有第二个判断arr[i][k] == 1其实都是一样的,因为咱们的数组当中只有1与0两个,大于零是1,等等于1还是1,所以是一样的。
全局控制:变量【i】,我们通过变量【i】来控制我们遍历的行数,这样就能逐一击破了。 初始点:坐标点需要从最左侧的0开始遍历,只要找到不是0的数就代表有链接点了。 下一个链接:坐标得从第N个开始遍历了,因为之前的已经遍历过了。这里的N是变量【j】。
/**
* 第一个连接点
* @param i
* @return
*/
private static int firstValue(int i) {
for (int j = 0; j < d_length; j++) {
if (arr[i][j] > 0) {
return j;
}
}
return -1;
}
/**
* 下一个连接点
* @param i
* @param j
* @return
*/
private static int nextValue(int i, int j) {
for (int k = (j + 1); k < d_length; k++) {
if (arr[i][k] == 1) {
return k;
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
DFSStart();
}
可以看到,输出内容与我们的目标结果是相同的,代表我们深度搜索的编码没有问题。
这个是我把类都复制了一下啊,你需要改一下包名以及你的类名即可进行测试。
package com.item.action;
public class Demo_def {
/**
* 顶点
*/
public static String d[] = { "1", "2", "3", "4", "5", "6", "7" };
/**
* 图转换数组
*/
public static int[][] arr= {
{0,1,1,0,0,0,0},
{1,0,0,1,1,0,0},
{1,0,0,0,0,1,0},
{0,1,0,0,0,0,1},
{0,1,0,0,0,0,0},
{0,0,1,0,0,0,0},
{0,0,0,1,0,0,0},
};
/**
* 顶点长度
*/
public static int d_length=d.length;
/**
* 记录每一个节点的遍历过程,走过则记录为true
*/
public static boolean[] isfStatus;
/**
* 开始递归
*/
public static void DFSStart() {
//初始化数组,记录使用过程
isfStatus = new boolean[d_length];
//遍历图数组
for (int i = 0; i < d_length; i++) {
//因为初始的布尔数组都是false,所以只要是false就是没有走过
if (isfStatus[i] == false) {
//进度到深度搜索的递归
DFS(i);
}
}
}
/**
* 递归深搜
* @param i
*/
private static void DFS(int i) {
// TODO Auto-generated method stub
System.out.print(d[i] + " ");
isfStatus[i] = true;
// 深度搜索子节点·从第一个节点到下一个节点
for (int j = firstValue(i); j >= 0; j = nextValue(i, j)) {
if (!isfStatus[j]) {
DFS(j);
}
}
}
/**
* 第一个连接点
* @param i
* @return
*/
private static int firstValue(int i) {
for (int j = 0; j < d_length; j++) {
if (arr[i][j] > 0) {
return j;
}
}
return -1;
}
/**
* 下一个连接点
* @param i
* @param j
* @return
*/
private static int nextValue(int i, int j) {
for (int k = (j + 1); k < d_length; k++) {
if (arr[i][k] == 1) {
return k;
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
DFSStart();
}
}
完整代码留在这里是帮助大家对照的啊,别直接复制用,这样意义就不那么高了。
我们咋做蓝桥杯题的时候很多的时候都是有套路的,我们很多时候通过我们背过的一些套路去套题目也会直接出结果的,例如全排列的方法,还有很多的公式,欧几里得,欧拉等等,都是很方便的,我们其实不是算法的创造者,我们只是知识的搬运工,争取将更多的知识搬运到咱们的大脑中啊。
下一篇我会好好准备一下BFS深度搜索,大家好好用用心是可以完全搞定的,加油。