《图的遍历试讲课件》由会员分享，可在线阅读，更多相关《图的遍历试讲课件（22页珍藏版）》请在金锄头文库上搜索。
1、图的遍历广度优先搜索算法,杨彦红 13466302868,回顾基本概念图及图的存储结构 广度优先算法的思想 广度优先算法内容 小结 作业,课堂内容安排,邻接矩阵 （不推荐） 邻接表 （推荐） 十字链表 （可以方便的获得入度和出度）,图及图的存储结构,0,2,1,5,4,3,6,7,0,1,2 ,1,0,3,4 ,2,0,5,6 ,3,1,7 ,4,1,7 ,5,2 ,6,2 ,7,3,4 ,动机： 社交网络，魔方求解，迷宫求解等 概念 图遍历是按照某种规则或次序访问图中各项点一次且仅一次的操作，亦是将网状结构按某种规则线性化的过程 。,图遍历的基本思想,动机： 社交网络，魔方求解，迷宫求解等
2、概念 图遍历是按照某种规则或次序访问图中各项点一次且仅一次的操作，亦是将网状结构按某种规则线性化的过程 。 问题 遵循什么样的规则？ 用什么表示点未访问还是已被访问？,图遍历的基本思想,动机： 社交网络，魔方求解，迷宫求解等 概念 图遍历是按照某种规则或次序访问图中各项点一次且仅一次的操作，亦是将网状结构按某种规则线性化的过程 。 问题 遵循什么样的规则？广度优先， 深度优先 用什么表示点未访问还是已被访问？增加节点状态变量,图遍历的基本思想,广度优先算法演示- first time,1、设初始时，所有的顶点均未被访问 2、从图中的某个顶点v0出发，访问v0，并依次访问v0的各邻接点 3、然后
3、分别从这些被访问的节点出发仍按照广度优先的策略搜索其他各点， 4、直到所有能访问的顶点都访问完为止。,0,2,1,5,4,3,6,7,0,1,2,3,4,5,6,7,技巧：用队列 Queue,(0, 1, 2, 3, 4, 5, 6, 7),Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False)
4、Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,0,1,2 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u
5、=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,0,1,2 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q);
6、 u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,0,1,2 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emp
7、tyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,0,1,2 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True;
8、 Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,1,0,3,4 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q);
9、 Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,1,0,3,4 ,Void BFS(Vnode G, i
10、nt v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,
11、2,0,5,6 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue / end void,广度优先算法演示-Se
12、cond time,0,2,1,5,4,3,6,7,Q,2,0,5,6 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while empty
13、queue / end void,广度优先算法演示-Second time,0,2,1,5,4,3,6,7,Q,3,1,7 ,Void BFS(Vnode G, int v) int u; Clearqueue (Q); Visit (G,v); visitedv=True; Enqueue(Q,v); while(! Emptyqueue (Q) v=Delqueue(Q); u=firstadj(G,v); while (u=0) if (visited(u)=False) Visit (G,u); visitedu=True; Enqueue (Q,u); u=nextadj(G,v,u) / end u /end while emptyqueue /
