最小生成树.ppt

*(遍历)(cont.)广度优先遍历----类似于树结构的层序遍历设图G的初态是所有顶点都“未访问过(False)”,在G中任选一个顶点v为源点,则广度优先搜索可定义为:①首先访问出发点v,并将其标记为“访问过(True)”;②接着依次访问所有与v相邻的顶点w1,w2…wt;③然后依次访问与w1,w2…wt相邻的所有未访问的顶点;④依次类推,直至图中所有与源点v有路相通的顶点都已访问过为止;⑤此时,从v开始的搜索结束,若G是连通的,则遍历完成;否则在G中另选一个尚未访问的顶点作为新源点,继续上述搜索过程,直到G中的所有顶点均已访问为止。*(遍历)(cont.)广度优先遍历示例广度优先遍历序列?入队序列?出队序列?v0v1v2v3v4v5v6v7v8v0v4v5v6v7遍历序列:v0v1v2v3v1v2v3v4v5v6v7v8v8队列v0v1v2v3v4v5v6v7v8生成森林*(遍历)(cont.)广度优先遍历特点:尽可能横向上进行搜索,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,故称先广搜索或广度优先搜索。先广或广度优先编号:搜索过程中,根据访问顺序给顶点进行的编号,称为先广或广度优先编号先广序列或BFS序列:先广搜索过程中,根据访问顺序得到的顶点序列,称为先广序列或BFS序列。生成森林(树):有原图的所有顶点和搜索过程中所经过的边构成的子图。先广搜索结果不唯一:即图的BFS序列、先广编号和生成森林不唯一。*(遍历)(cont.)广度优先遍历主算法:boolvisited[NumVertices];//访问标记数组是全局变量intdfn[NumVertices];//顶点的先深编号voidBFSTraverse(AdjGraphG)//主算法//*先广搜索一邻接表表示的图G;而以邻接矩阵表示G时,算法完全相同{inti,count=1;for(inti=0;i<;i++)visited[i]=False;//标志数组初始化for(inti=0;i<;i++)if(!visited[i])BFSX(G,i);//从顶点i出发的一次搜索,DFSX(G,i)}*(遍历)(cont.)从一个顶点出发的一次广度优先遍历算法:实现步骤:;;visited[v]=1;顶点v入队Q;(队列Q非空)=队列Q的队头元素出队;=顶点v的第一个邻接点;(w存在),则访问顶点w;visited[w]=1;顶点w入队列Q;=顶点v的下一个邻接点;*(遍历)(cont.)voidBFS1(AdjGraph*G,intk)//这里没有进行先广编号{inti;EdgeNode*p;QueueQ;MakeNull(Q);cout<<G→vexlist[k].vertex;visited[k]=True;EnQueue(k,Q);//进队列while(!Empty(Q)){//队空搜索结束i=DeQueue(Q);//vi出队p=G→vexlist[i].firstedge;//取vi的边表头指针while(p){//若vi的邻接点vj(j=p→adjvex)存在,依次搜索 if(!visited[p→adjvex]){//若vj未访问过 cout<<G→vexlist[p→adjvex].vertex;//访问vjvisited[p→adjvex]=TRUE;//给vj作访问过标记EnQueue(p→adjvex,Q);//访问过的vj入队} p=p→next;//找vi的下一个邻接点}//重复检测vi的所有邻接顶点}//外层循环,判队列空否}//以vk为出发点时对用邻接表表示的图G进行先广搜索*(遍历)(cont.)voidBFS2(MTGraph*G,intk)//这里没有进行先广编号{inti,j;QueueQ;MakeNull(Q);cout<<G→vexlist[k];//访问vkvisited[k]=True;//给vk作访问过标记EnQueue(k,Q);//vk进队列while(!Empty(Q)){//队空时搜索结束i=DeQueue(Q);//vi出队for(j=0;j<G→n;j++){//依次搜索vi的邻接点vj if(G→edge[i][j]==1&&!visited[j]){//若vj未访问过 cout<<G→vexlist[j];//访问vjvisited[j]=True;//给vj作访问过标记EnQueue(j,Q);//访问过的vj入队}}//重复检测vi的所有邻接顶点}//外层循环,