asp.net2.0网站开发全程解析 pdf建站模板外贸

asp.net2.0网站开发全程解析 pdf,建站模板外贸,小米手机优化,做模板网站的公司各位读者大佬好#xff0c;我是落羽#xff01;一个坚持不断学习进步的学生。 如果您觉得我的文章还不错#xff0c;欢迎多多三连分享交流#xff0c;一起学习进步#xff01; 欢迎关注我的blog主页: 落羽的落羽 文章目录一、图的遍历1. BFS2. DFS3. 测试二、图的最小生…各位读者大佬好我是落羽一个坚持不断学习进步的学生。如果您觉得我的文章还不错欢迎多多三连分享交流一起学习进步欢迎关注我的blog主页:落羽的落羽文章目录一、图的遍历1. BFS2. DFS3. 测试二、图的最小生成树算法1. Kruskal算法2. Prim算法一、图的遍历遍历一个图针对的是遍历所有顶点。主要是两种思路广度优先BFS和深度优先DFS上一篇文章讲过了图可以用领接矩阵和领接表存储边我们以领接矩阵的模版进行讲解1. BFS图的广度优先遍历思路是从起始顶点出发先访问当前顶点的所有直接邻接顶点一层再依次访问这些邻接顶点的邻接节点下一层以此类推直到遍历完所有可达顶点。曾经我们讲二叉树的广度优先遍历时是利用了队列结构这里也是一样的。每次队头元素出队列时队头元素顶点的所有领接顶点全部入队列。为了防止一个顶点多次遍历还需要一个数组用于标记。// 参数是遍历的起始顶点voidBFS(constVsrc){// 得到起始顶点的下标size_t srcindexGetVertexIndex(src);// 防止一个顶点被多次遍历用一个数组标记被遍历过的下标vectorboolvisited;visited.resize(_vertexs.size(),false);// 起点入队列queueintq;q.push(srcindex);visited[srcindex]true;coutBFS遍历: ;while(!q.empty()){size_t frontq.front();// 打印出当前遍历顶点cout_vertexs[front] ;// 队头元素出队列q.pop();// 队头元素顶点所有没遍历过的相邻顶点入队列在领接矩阵中查询相邻顶点for(size_t i0;i_vertexs.size();i){if(visited[i]false_matrix[front][i]!MAX_W){// 遍历过的顶点标记为truevisited[i]true;q.push(i);}}}// 如果该图不是连通图这种方法会使某些顶点没遍历到for(boolcheck:visited){if(checkfalse){cout该图不是连通图还有未遍历到的顶点;}}coutendl;}2. DFS图的深度优先遍历核心思想是 “一条路走到黑”从起始顶点出发沿着一条路径尽可能深地探索直到无法继续遇到已访问节点或无邻接顶点再回溯到上一个顶点继续探索其他未走的分支。为了防止一个顶点多次遍历也需要一个数组用于标记。void_DFS(size_t srcIndex,vectorboolvisited){// 当前遍历顶点cout_vertexs[srcIndex] ;visited[srcIndex]true;// 找srcIndex的相邻顶点遍历下去for(size_t i0;i_vertexs.size();i){if(visited[i]false_matrix[srcIndex][i]!MAX_W){_DFS(i,visited);}}}voidDFS(constVsrc){// 得到起始顶点的下标size_t srcindexGetVertexIndex(src);// 防止一个顶点被多次遍历用一个数组标记被遍历过的下标vectorboolvisited;visited.resize(_vertexs.size(),false);coutDFS遍历: ;_DFS(srcindex,visited);coutendl;}3. 测试我们用这张图进行测试完整代码#pragmaonce#includeiostream#includevector#includemap#includequeueusingnamespacestd;// 邻接矩阵 图namespaceMatrix{// V顶点类型 W边权值类型 MAX_W表示边不存在的值 Direction表示图是否有向templateclassV,classW,W MAX_WINT_MAX,boolDirectionfalseclassGraph{public:Graph(constV*vertexs,size_t n){_vertexs.reserve(n);for(size_t i0;in;i){_vertexs.push_back(vertexs[i]);_vIndexMap[vertexs[i]]i;}// MAX_W 作为不存在边的标识值// 初始化时默认没有边边需要一条一条手动添加用AddEdge函数_matrix.resize(n);for(autoe:_matrix){e.resize(n,MAX_W);}}// 找到一个顶点的映射下标size_tGetVertexIndex(constVv){autoret_vIndexMap.find(v);if(ret!_vIndexMap.end()){returnret-second;}else{throwinvalid_argument(不存在的顶点);return-1;}}// 添加一条边src和dst代表两端顶点w是权值voidAddEdge(constVsrc,constVdst,constWw){size_t srciGetVertexIndex(src);size_t dstiGetVertexIndex(dst);_matrix[srci][dsti]w;//如果是无向图则[dsti][srci]也需添加边if(Directionfalse){_matrix[dsti][srci]w;}}// 参数是遍历的起始顶点voidBFS(constVsrc){// 得到起始顶点的下标size_t srcindexGetVertexIndex(src);// 防止一个顶点被多次遍历用一个数组标记被遍历过的下标vectorboolvisited;visited.resize(_vertexs.size(),false);// 起点入队列queueintq;q.push(srcindex);visited[srcindex]true;coutBFS遍历: ;while(!q.empty()){size_t frontq.front();// 打印出当前遍历顶点cout_vertexs[front] ;// 队头元素出队列q.pop();// 队头元素顶点所有没遍历过的相邻顶点入队列在领接矩阵中查询相邻顶点for(size_t i0;i_vertexs.size();i){if(visited[i]false_matrix[front][i]!MAX_W){// 遍历过的顶点标记为truevisited[i]true;q.push(i);}}}// 如果该图不是连通图这种方法会使某些顶点没遍历到for(boolcheck:visited){if(checkfalse){cout该图不是连通图还有未遍历到的顶点;}}coutendl;}void_DFS(size_t srcIndex,vectorboolvisited){// 当前遍历顶点cout_vertexs[srcIndex] ;visited[srcIndex]true;// 找srcIndex的相邻顶点遍历下去for(size_t i0;i_vertexs.size();i){if(visited[i]false_matrix[srcIndex][i]!MAX_W){_DFS(i,visited);}}}voidDFS(constVsrc){// 得到起始顶点的下标size_t srcindexGetVertexIndex(src);// 防止一个顶点被多次遍历用一个数组标记被遍历过的下标vectorboolvisited;visited.resize(_vertexs.size(),false);coutDFS遍历: ;_DFS(srcindex,visited);coutendl;}private:mapV,size_t_vIndexMap;// 每个顶点映射一个下标vectorV_vertexs;// 顶点集合vectorvectorW_matrix;// 领接矩阵 存储边};}intmain(){chararr[]{C,A,D,B,E};Matrix::Graphchar,intgraph(arr,sizeof(arr)/sizeof(char));// 添加边权值不用管随便写的graph.AddEdge(A,D,1);graph.AddEdge(D,B,2);graph.AddEdge(D,E,3);graph.AddEdge(B,E,4);graph.AddEdge(B,C,5);graph.BFS(A);graph.BFS(B);graph.DFS(A);graph.DFS(B);return0;}结果分析符合BFS与DFS的规则二、图的最小生成树算法连通图的每一棵生成树都是原图的一个极大无环子图。最小生成树就是指所有边的权值加起来总权最小的生成树可以理解为用最小的成本构成的生成树。最小生成树也是生成树要符合要包括原图的所有顶点只能使用原图中的边来构造只能使用恰好n-1条边来连接图中n个顶点选择的n-1条边不能构成回路边的总权值要最小构造最小生成树一般有两种算法克鲁斯卡尔Kruskal算法、普里姆Prim算法都是用了逐步求解的贪心策略。1. Kruskal算法这种算法的思路是“从小到大选边”将所有边按权值从小到大排序依次选择最小的边若这条边连接的两个顶点不在同一个已连通集合中就将这条边加入生成树否则跳过避免形成环。重复此过程直到选够n−1条边。判断两个顶点是否在一个已连通集合可以利用并查集详见并查集的原理与使用typedefGraphV,W,MAX_W,DirectionSelf;structEdge{V _srci;V _dsti;W _w;Edge(constVsrci,constVdsti,constWw):_srci(srci),_dsti(dsti),_w(w){}booloperator(constEdgeeg)const{return_weg._w;}booloperator(constEdgeeg)const{return_weg._w;}};Graph()default;// 传递一个图作为构造最小生成树的结果。返回总权值WKruskal(SelfminTree){// 所有顶点拷贝初始不带任何边minTree._vertexs_vertexs;minTree._vIndexMap_vIndexMap;minTree._matrix.resize(_vertexs.size());for(autoe:minTree._matrix){e.resize(_vertexs.size(),MAX_W);}// priority_queue用于按照权值排序边priority_queueEdge,vectorEdge,greaterEdgepq;for(size_t i0;i_matrix.size();i){for(size_t j0;j_matrix[i].size();j){// 无向图只要判断领接矩阵一半的边if(ij_matrix[i][j]!MAX_W){pq.push(Edge(i,j,_matrix[i][j]));}}}// 记录总权值W totalW();// 贪心算法从最小的边开始选将选出的边两端顶点放入一个集合// size记录已选出边数intsize0;UnionFindSetufs(_vertexs.size());while(!pq.empty()){Edge minpq.top();pq.pop();// 边两端顶点不在一个集合说明不会构成环则添加这条边到最小生成树两个顶点放到一个集合if(ufs.FindRoot(min._srci)!ufs.FindRoot(min._dsti)){minTree.AddEdge(min._srci,min._dsti,min._w);totalmin._w;size;ufs.Union(min._srci,min._dsti);}}// 若size不等于n-1说明构建最小生成树失败返回一个默认值W()if(size_vertexs.size()-1){returntotal;}else{returnW();}}2. Prim算法Prim算法是按点贪心X集合存放已连入生成树的点Y集合存放未连入生成树的点。一开始所有顶点都在Y中首先将参数起点放入X并从Y中删除。从X中所有点连出的边中选出“权最小的且有一端顶点在Y中的边”插入到最小生成树中再把这条边的端点放入X中并从Y中删除。如此循环往复直到所有顶点都在X中。这种算法天然避免了环的发生// 给一个起点WPrim(SelfminTree,constVsrc){size_t srciGetVertexIndex(src);size_t n_vertexs.size();minTree._vertexs_vertexs;minTree._vIndexMap_vIndexMap;minTree._matrix.resize(n);for(size_t i0;in;i){minTree._matrix[i].resize(n,MAX_W);}// X和Y集合vectorboolX(n,false);vectorboolY(n,true);X[srci]true;Y[srci]false;// 从X-Y集合中连接的边里面选出最小的边priority_queueEdge,vectorEdge,greaterEdgeminq;// 先把srci连接的边添加到队列中for(size_t i0;in;i){if(_matrix[srci][i]!MAX_W){minq.push(Edge(srci,i,_matrix[srci][i]));}}size_t size0;W totalW();while(!minq.empty()){Edge minminq.top();minq.pop();if(!X[min._dsti]){minTree.AddEdge(min._srci,min._dsti,min._w);X[min._dsti]true;Y[min._dsti]false;size;totalmin._w;if(sizen-1)break;for(size_t i0;in;i){if(_matrix[min._dsti][i]!MAX_WY[i]){minq.push(Edge(min._dsti,i,_matrix[min._dsti][i]));}}}}if(sizen-1){returntotal;}else{returnW();}}本篇完感谢阅读