昆明疫情最新情况今天前端seo优化
一.广度优先遍历的基本思想
（1）访问顶点v；
（2）依次访问v的各个未被访问的邻接点v1，v2，v3……，vk；
（3）分别从v1，v2，v3……，vk出发依次访问他们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。
二.广度优先遍历的伪代码
1.初始化队列Q；
2.访问顶点v；visited[v]=true;顶点v入队列Q；
3.while（队列Q非空）
3.1 v=队列Q的队头元素出队；
3.2 w=顶点v的第一个邻接点；
3.3while（w存在）
3.3.1 如果w未被访问，则访问顶点w；visited[w]=1;顶点w入队；
3.3.2 w=顶点v的下一个邻接点
三.代码实现
template<class T>
void MGraph<T>::BFSTraverse(int v){bool visited[vertexNum]=false;queue<int> Q;int w,i=0,count=0;cout<<vertex[v]<<endl;visited[v]=true;++count;Q.push(v);if(count==vertexNum){return;}while(!Q.empty()){v=Q.front();//队头元素出队Q.pop();for(i=0;i<vertexNum;i++){if(arc[v][i]&&!visited[i]){//w未被访问w=i;cout<<vertex[w]<<endl;visited[w]=true;++count;Q.push(w);}}}}template <class T>
void ALGraph<T>::BFSTraverse(int v){bool visited[vertexNum]=false;queue<int> Q;int w,i=0,count=0;cout<<adjList[v].vertex<<endl;visited[v]=true;++count;Q.push(v);if(count==vertexNum){return;}while(!Q.empty()){v=Q.front();//队头元素出队Q.pop();struct ArcNode *p=adjList[v].firstEdge;while(p){if(!visited[p->adjvex]){w=p->adjvex;cout<<adjList[w].vertex<<endl;visited[w]=true;++count;Q.push(w);}else{p=p->next;}}}
}
四.总结
广度优先：确定起始节点后，全部邻接点（分支）同时开始遍历；
深度优先：先从一个邻接点（分支）开始遍历，直至该分支全部遍历完成，再遍历按顺序的下一个分支。