www.whkt.net > 广度优先搜索例题

广度优先搜索例题

广度优先就是一层一层的往下访问,该层从左到右访问结束之后再访问下一层,这里以二叉树为例,用数组存放该二叉树,根节点位置定为1(零号位置不用,你也可以用,这不规定,我这里不用而已)结构如下:12 34 5 6 78 9 10 11 12 13 14

非原创~转的:#include <stdio.h> #include <string.h> #define max 500 int map[max][max]; /*标记两个顶点是否相邻, 是则1, 否则0*/ int visited[max]; /*标记节点是否访问,是则1, 否则0*/ int bfs (int v, int n) { int j, k, maxsize, front, rear; int

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图.在深度优先搜索中,对于最新发现的结点,如果它还有以此为起点而未搜过的边,就沿着边继续搜索下去.当结点v的所有边都已被探寻过,搜索将回溯到发现结点v有那条边的始结点.

(1)在产生新的子结点时,深度越小的结点越先得到扩展,即先产生它的子结点.为使算法便于实现,存放结点的数据库一般用队列的结构.(2)无论问题性质如何不同,利用广度优先搜索法解题的基本算法是相同的,但数据库中每一结点内容,

广度优先一般就是使用队列,创建一个队列,然后开始搜索起始点四周的结点加入队列,搜完一个结点后作出标记避免重复搜索,接着出队列继续搜索,知道搜索完队列内的结点.广度优先就是先搜索四周的慢慢向四周扩展.

深度:DGEBHFCA 广度:abdgcefh

深度优先搜索:从图的某顶点出发,依次访问该顶点的邻接点广度优先搜索:类似树的按层次遍历 依次访问某顶点各个未访问的顶点.算法可参考数据结构书.非常详细!

广度

你可以画一个类似于这样的表:1->2->3->4 (表示1可达到2,达到3,达到4)2->1->3->53->1->2->4->5->64->1->3->65->2->3->66->3->4->5 广度优先搜索就是把每一行按照顺序输出,去掉重复的,即先看1,有1,2,3,4,然后看2,因为有3,4了,所以只要5,然后看3,以此类推..一行行来.深度优先搜索,是先看1,然后1可以到2,然后直接看2,2可以到3,5随便选一个都可以,我们到3好了,然后看3的那行可以到1,2,4,5,6随便选一个都可以,不过要去掉重复的,以此类推.可以排出很多种的..

空间状态搜索:(0,0,0,0) --->(1,1,1,1),每个位置依次代表,羊,狼,菜,农夫.0表示没过,1表示过河了.bfs 十六个方向搜吧,排除一下不允许出现的情况比如(0,0,1,1)等.

网站地图

All rights reserved Powered by www.whkt.net

copyright ©right 2010-2021。
www.whkt.net内容来自网络,如有侵犯请联系客服。zhit325@qq.com