~文轩~
2022-03-20 22:06
采纳率: 100%
浏览 64

图的广度优先遍历的时间复杂度为什么不是O(max{n,e})呢(语言-c++)

时间复杂度是由一个算法中执行次数最多的语句来确定的吧,那么图的以邻接表为存储形式的广度优先遍历应该由哪个语句才能得出时间复杂度为o(n+e)呢?(我可以理解他遍历了所有顶点和边,但是它每遍历一个顶点的同时也遍历了一条边,所以我觉得应该取n和e的最大值,而不是他们相加)

img

img

图片转代码服务由CSDN问答提供 功能建议

 3)当队列为空时跳出循环,广度优先搜索即完成.
 以邻接表为存储结构的广度优先搜索遍历算法如下:
 //visit数组被初始化为全0
        ArcNode *pi
        int que[maxSizel,front=0,rear=0;//这是队列定义的简单写法
         intji
         Visit(v)i                                                                             //任意访问顶点的函数
         visit|vJ=l;
                                                                                     //当前顶点进队
         rear=(rear+1)maxSize;
         que[rearl=V;
                                                                                     //队空的时候说明遍历完成
         While(front!=rear)
 front=(front+1) %maxSize;                                                                          //顶点出队
 j=que[frontl;
 p=G->adjlist[jl.firstarci                                                                           //p指向出队顶点的第一条边
                                                                          //将p的所有邻接点中未被访问的入队
 while(p!=NULL)
        if(visit[p->adjvex]==0)                                                                  //当前邻接顶点未被访问,则进队
                Visit(p->adjvex);
                visit[p->adjvexl=1;
                rear=(reart1) %maxSize;                                                         //该顶点进队
                que【rearl=p->adjvex;
      p=p->nextarc;
                                                                          //p指向的下一条边
                                 王不同外,其他都十分类似

1条回答 默认 最新

相关推荐 更多相似问题