基于c语言的广度优先搜索

《基于c语言的广度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于C语言的广度优先搜素算法的实现1.算法说明广度优先搜索使用队列(queue)来实现，整个过程也可以看做一个倒立的树形：(1)把根节点放到队列的末尾。(2)每次从队列的失部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。(3)找到所要找的元素吋结束程序。(4)如果遍历整个树还没有找到，结束程序。本次算法的应用中，我用这个队列来保存最短路径。首先我定义队列为“真进假出”，所谓“真进”就是当添加一个元素时，把元素放置队尾，然后rear++，而“假出”就是当删除一个元素吋，并没有真的删除队首

2、元素，只是front++。通过比较搜索所得的所有可行路径的长度，这样我们就可以从队列屮获取一条最短路径！1.代码及结果^includeftdefineNtypcdcfstruct{intx;inty;}Node;/*双?亲X的?序6号?*//*双?亲X的?序d号?*//*孩C子哩？的?坐?标括?//*队6元a素?类无？型i*/typcdcfstruct{intparent:intchild;Nodechi1dpos:}QType;intMaze[N][N]={1111111111111111111intvisitcd[N]

3、[N]={1，11111111，1，1，1，1，1，1，1，1，1，1，1，1，10,0,0,1，0,0,0,1，1,0,0,1，0,00,0,1,0,0,0,0,1,0,0,0,0,1,10,0,0,0,0,0,1,0,0,1,0,0,0,11,0,1,0,0,0,0,0,0,0,0,1,0,00,0,0,0,1,0,0,0,0,1,0,0,0,01，0,0,0,0,1，1，0,1,0,0,1，0,11,0,0,1,0,0,0,1,0,1,0,0,0,00,0,1,0,1,0,1,0,1,0,0,0,1,11,0,0,0,0,0,1,0,

4、0,0,1,0,0,00,0,0,1,0,0,0,0,1,0,0,1,1,01,1,1,0,1,0,0,1,0,1,0,0,0,10,0,1,0,0,0,1,0,0,1,0,0,0,00,1,1,1,1,1,0,0,0,1,0,0,1,01,0,0,0,0,0,1,0,0,1,0,0,0,10,0,0,1,0,0,0,0,1,0,0,0,0,01,0,0,1，0,1，0,0,1,0,0,1，0,00,0,0,1,0,0,0,1,0,0,1,0,0,01,0,0,0,1,0,0,0,1,0,0,0,1,01,1,1,1,1,1,1,1,1,1

5、,1,1,1,11，1，1，1，1，1，1，1，1，1，1，1，1，1，0,0,0,1,0,0,0,1,1,0,0,1,0,00,0,1,0,0,0,0,1,0,0,0,0,1,10,0,0,0,0,0,1,0,0,1,0,0,0,11,0,1,0,0,0,0,0,0,0,0,1,0,00,0,0,0,1,0,0,0,0,1,0,0,0,01,0,0,0,0,1,1,0,1,0,0,1,0,11,0,0,1,0,0,0,1,0,1,0,0,0,00,0,1,0,1,0,1,0,1,0,0,0,1,11,1,1,1,1,0,0,0,1,1,1

6、,0,0,0,1,0,1,0,0,1,0,0,0,0,1,1,0,0,1,1,0,1,0,0,1,0,0,0,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,1,1,0,1,1,1，1，1,0,1,0,0,0,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,0,1,0,1,1,1,1,1,1}0,0,0,1,11,0,0,0,10,1,0,0,10,0,0,0,11,0,0,1,10,1,0,0,10,0,0,1,11,0,0,0,11,1,0,0,0,0,0,1,0,0,0,

7、1,0,0,0,0,1,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,1,0,1,0,0,0,1,1,1,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,1,0,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,0,1,0

8、,0,1,0,0,1,0,0,0,1,0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0,