图的遍历试讲课件.ppt

图的遍历——广度优先搜索算法杨彦红yangyanhong1012@**********回顾基本概念——图及图的存储结构广度优先算法的思想广度优先算法内容小结作业课堂内容安排邻接矩阵(不推荐)邻接表(推荐)十字链表(可以方便的获得入度和出度)图及图的存储结构02154367012^1034^2056^317^417^52^62^734^动机:社交网络,魔方求解,迷宫求解等概念图遍历是按照某种规则或次序访问图中各项点一次且仅一次的操作,亦是将网状结构按某种规则线性化的过程。图遍历的基本思想动机:社交网络,魔方求解,迷宫求解等概念图遍历是按照某种规则或次序访问图中各项点一次且仅一次的操作,亦是将网状结构按某种规则线性化的过程。问题遵循什么样的规则?用什么表示点未访问还是已被访问?图遍历的基本思想动机:社交网络,魔方求解,迷宫求解等概念图遍历是按照某种规则或次序访问图中各项点一次且仅一次的操作,亦是将网状结构按某种规则线性化的过程。问题遵循什么样的规则?——广度优先,深度优先用什么表示点未访问还是已被访问?——增加节点状态变量图遍历的基本思想广度优先算法演示-firsttime1、设初始时,所有的顶点均未被访问2、从图中的某个顶点v0出发,访问v0,并依次访问v0的各邻接点3、然后分别从这些被访问的节点出发仍按照广度优先的策略搜索其他各点,……,4、直到所有能访问的顶点都访问完为止。0215436701234567技巧:用队列Queue(0,1,2,3,4,5,6,7)VoidBFS(VnodeG[],intv){intu;Clearqueue(Q);Visit(G,v);visited[v]=True;Enqueue(Q,v);while(!Emptyqueue(Q)){v=Delqueue(Q); u=firstadj(G,v); while(u>=0) { if(visited(u)==False) {Visit(G,u);visited[u]=True;Enqueue(Q,u); u=nextadj(G,v,u) } }//endu }//endwhileemptyqueue}//endvoid广度优先算法演示-Secondtime021543670Q012^VoidBFS(VnodeG[],intv){intu;Clearqueue(Q);Visit(G,v);visited[v]=True;Enqueue(Q,v);while(!Emptyqueue(Q)){v=Delqueue(Q); u=firstadj(G,v); while(u>=0) { if(visited(u)==False) {Visit(G,u);visited[u]=True;Enqueue(Q,u); u=nextadj(G,v,u) } }//endu }//endwhileemptyqueue}//endvoid广度优先算法演示-Secondtime021543670Q0012^VoidBFS(VnodeG[],intv){intu;Clearqueue(Q);Visit(G,v);visited[v]=True;Enqueue(Q,v);while(!Emptyqueue(Q)){v=Delqueue(Q); u=firstadj(G,v); while(u>=0) { if(visited(u)==False) {Visit(G,u);visited[u]=True;Enqueue(Q,u); u=nextadj(G,v,u) } }//endu }//endwhileemptyqueue}//endvoid1广度优先算法演示-Secondtime02154367Q012^