专业的建设企业网站公司合肥小程序建设

专业的建设企业网站公司,合肥小程序建设,常用网站开发技术和工具,简述如何优化网站的方法BFS 基本步骤 要实现图的广度优先遍历#xff0c;需要借助队列这一结构。 将入口顶点入队#xff0c;同时标记为已访问若队列不为空#xff0c;则从队列中取出一个顶点访问检查与该顶点相连的其它顶点#xff0c;若没有被访问过则入队#xff0c;同时标记为已访问重复2、3…BFS基本步骤要实现图的广度优先遍历需要借助队列这一结构。将入口顶点入队同时标记为已访问若队列不为空则从队列中取出一个顶点访问检查与该顶点相连的其它顶点若没有被访问过则入队同时标记为已访问重复2、3步骤示例代码下面举一个例子#includeiostream#includevector#includequeuestd::vectorstd::vectorintg_Graph;staticvoidInput(){intvertexNums,edgeNums;std::cinvertexNumsedgeNums;g_Graph.resize(vertexNums1,std::vectorint(vertexNums1));intfrom,to,weight;for(size_t i0;iedgeNums;i){std::cinfromtoweight;g_Graph[from][to]weight;g_Graph[to][from]weight;}}staticvoidBFS(){std::vectorboolvisited(g_Graph.size(),false);std::queueintqueue;queue.push(1);visited[1]true;intvertex;while(!queue.empty()){vertexqueue.front();queue.pop();std::coutvertex ;for(size_t i1;ig_Graph.size();i){if(!visited[i]g_Graph[vertex][i]!0){queue.push(i);visited[i]true;}}}std::coutstd::endl;}intmain(){Input();BFS();return0;}读者可以用这个代码自行测试。BFS与无权图最短路径查找BFS可以用于查找无权图的最短路径。BFS是层层递进进行遍历的第一次访问某一个顶点的时候此时经过的路径就是从起始顶点到该顶点的最短路径。下面是示例代码staticstd::vectorstd::vectorintg_Graph;staticvoidBFSGetShortestPath(intstart,inttarget){std::vectorboolvisited(g_Graph.size(),false);std::queueintqueue;std::vectorintparent(g_Graph.size(),-1);// 用于回溯路径下标为顶点元素为其上一个顶点queue.push(start);visited[start]true;intvertex;while(!queue.empty()){vertexqueue.front();queue.pop();if(vertextarget)// 如果当前访问的顶点是目标顶点{std::vectorintpath;intcursortarget;while(cursor!-1)// 通过parent获得路径{path.push_back(cursor);cursorparent[cursor];}std::reverse(path.begin(),path.end());// 反转之后得到正确的路径for(autoa:path)std::couta ;std::coutstd::endl;return;}for(size_t i1;ig_Graph.size();i)// 正常的BFS遍历操作{if(visited[i]falseg_Graph[vertex][i]!0)// 遍历vertex的邻接顶点{queue.push(i);visited[i]true;parent[i]vertex;}}}}