图的遍历教学课件.ppt

第11章图*,:人工智能搜索最短路径问题*图的遍历从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索遍历应用举例*图的遍历(2)为了保证访问所有顶点:voidgraphTraverse(constGraph*G){for(v=0;v<G->n();v++)G->setMark(v,UNVISITED);//Initializefor(v=0;v<G->n();v++)if(G->getMark(v)==UNVISITED)doTraverse(G,v);}*从图中某个顶点V0出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图连通图的深度优先搜索遍历*Vw1SG1SG2SG3W1、W2和W3均为V的邻接点,SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V:for(W1、W2、W3)若该邻接点W未被访问,则从它出发进行深度优先搜索遍历。w2w3w2*从上页的图解可见:;解决的办法是:为每个顶点设立一个“访问标志”。?*深度优先搜索(2)Cost:(|V|+|E|).*深度优先搜索DFS(1)//DepthfirstsearchvoidDFS(Graph*G,intv){PreVisit(G,v);//TakeactionG->setMark(v,VISITED);for(intw=G->first(v);w<G->n();w=G->next(v,w))if(G->getMark(w)==UNVISITED)DFS(G,w);PostVisit(G,v);//Takeaction}*首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点,如果未被访问,则以该顶点为起始点,进行深度优先搜索遍历,否则继续检查下一顶点。非连通图的深度优先搜索遍历