广度优先搜索和深度优先搜索都可以用于遍历一棵树（广度优先搜索怎么遍历）



        图的广度优先遍历和树的广度优先遍历类似，树是层序遍历，从根节点出发找到其所有的孩子结点。而图的广度优先就是从一个结点开始，搜索所有的相邻节点。而图与树不同点在于，树不存在回路，所以搜索相邻的结点不会搜到已经访问过的结点，而图搜索相邻顶点时可能会重复访问。所以，图需要对每个顶点进行标记。

        那么具体如何实现对图的广度优先遍历呢？之前了解到，树的层序遍历需要一个辅助队列，BFS也是采取类似的方法。这里我们主要用到两个图的基本操作，一个是寻找第一个相邻节点FirstNeighbor，一个是寻找相邻节点的下一个相邻节点NextNeighbor。同时定义一个bool型的数组visited[]标记每个顶点有没有被访问过。

算法如下：

void BFS(G,v){   //从顶点v出发遍历图G

    visit(v);

    visited(v)=true;

    Enqueue(Q,v);        //v进入队列Q

    while(isempty(Q)){ //队列非空

        Dequeue(Q,v);  //队头出队

        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor){ //遍历与队头顶点相邻的所有顶点

            if(!visited(w)){ //邻接节点没有被访问过

                visit(w);

                visited(w)=true;

                Enqueue(Q,w); //访问并入队

                                }

                    }

        }

}

        总体来看，广度优先遍历和层序遍历从实现方式来看十分类似（因为树其实就是一个特殊的图），只是要记住广度优先遍历每次访问完需要标记，访问时也要排除掉标记的。但是图的存储方式不同遍历的次序也是不同的，邻接表的遍历次序是唯一的。

        并且此方法对于非连接图的遍历也存在弊端，不过只需在遍历停止后，再遍历一遍visited[]数组，如果存在数组值为false，在以该节点为起始节点进行BFS遍历，直到没有没访问的节点即可。实现方法如下：

void BFSTraverse(G){

for(i=0;i<G.vexnum;i++)visited[i]=false; //初始化visited数组

InitQueue(Q);

for(i=0;i<G.vexnum;i++){

        if(visited[i]==false){ 

            BFS(G,i);

                }

}

}

        显然对于无向图，调用BFS的次数=连通分量数。BFS的空间复杂度，辅助队列最大为O（|v|）。此算法的主要开销来自于访问顶点和找到相邻的邻接点，对于邻接矩阵，寻找顶点邻接点的时间复杂度为O(v)，共有v个顶点因而查找所有顶点的邻接点的时间复杂度为O（v^2）。对于邻接表，查找每个顶点的邻接点只需O(E)的时间复杂度，总时间复杂度为O(V+E)。

        在了解了广度优先搜索的原理后，下面我们开始学习其最重要的一个应用——求最短路径。最短路径问题有几个常见的场景：单源最短路径，每对顶点间的最短路径。BFS可以用来求无权图的单元最短路径。

void BFS_Min_Distance(G,u){

visited(u)=true;

for(i=0;i<G.vexnum;i++){d[i]=-1;

path[i]=-1;

}//初始化路径长度和路径前驱节点

d[u]=0;

EnQueue(Q,u);

while(isEmpty(Q)){

DeQueue(Q,u);//队头元素出队

for(w=FirstNeigobor(G,u);w>=0;w=NextNeighbor(G,u,w)){//访问邻接节点

while(!visited[w]){

d[w]=d[u]+1;

path[w]=u;

visited[w]=true;

EnQueue(Q,w);}

        }//if

    }//while

}

通过回溯path数组，我们可以找到最短路径，多么精妙的算法。同时我们可以发现，通过广度优先生成树的节点和根节点的距离就是最短路径。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/19362.html