Skip to content

Latest commit

 

History

History
 
 

10

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 

广度优先和深度优先算法

这两种算法都是针对的图,来进行定义的。

方法就是 首先我们先new一个Graph,然后这Graph的是用一个数组和一连串的链表(或者更换成跳表都可以,或者二叉查找树,平衡二叉查找树都可以) 然后这样就组成了一个图。这种方法是 链表法 我们如果使用数组法的话就是使用一个二维数组即可。

广度优先

按照每一层一层一层的往下走,这其中的每一层借助一个队列,把这一层中的所有数据放入队列中,去掉一个就出列一个,然后一直把这个顶点中的顶点(没有访问过的)放入队列中,直到队列结束,并且发现了值,因为广度优先是一层一层的遍历,相当于严格按照层级划分,所以压根不用递归,也就不会有多叉树 而且因为很标准的往下走,并且运行两次他们走的路径绝对是一模一样,所以找到的解释一样的解,并且是最短路径。

深度优先

深度优先的核心是递归,也就是多叉树,也就是说,它会寻找所有跟自己有关的,以及跟自己的子顶点有关的,,,,,然后因为我们设定了一个值 也就是说必须是叉有必须是没有访问过的,才可以,那么如果一个顶点走投无路了,跟她相邻的都已经访问过了,它就进入了死点,那么这条路就死了,自然的抛弃罢了,因为还有很多条路径,因为是多叉树吗,这个时候看谁最快的找到b那么就返回即可。

深度优先,是递归,如果画出它的递归树,那么这个数是一个叉不规则的多叉树,看哪一个叉子成功找到就可以了,所以它会发生运行几次结果不一样的现象,也正常,毕竟得出来的结果很随机,而且不一定是最短路径。

走迷宫

其实走迷宫就可以使用深度优先来解决,其实用广度也是可以的,因为走迷宫可以抽象为给出0然后让你找出某个点,所以深度和广度都是可以的。

树和图

顺便说一下,树和图这两种结构都是非线性结构,其实你可以把树看成图的一种,你可以画个图,其实树就是一种图,并且比图还更简单 所以如果我们要实现BFS和WFS 把树当做图就可以了,原理是一样的。

比如在BFS和WFS中我们的每个顶点都是有一个链表的,然后里面储存的是跟它有关系的顶点,那树也是一样的啊,你可以把它当做 一个无向图,然后将子节点当做父节点的相关联的图即可,然后一步一步的输入每个节点的那个链表中,接下来BFS和WFS就跟图的广义上的 做法是一样的啦。