做网站时如何上传图片,codewars网站,如何选择宜昌网站建设,wordpress怎么编辑表格目录 1.图的遍历1.广度优先遍历2.深度优先遍历 2.最小生成树1.Kruskal算法2.Prim算法 1.图的遍历
给定一个图G和其中任意一个顶点 v 0 v_0 v0#xff0c;从 v 0 v_0 v0出发#xff0c;沿着图中各边访问图中的所有顶点#xff0c;且每个顶 点仅被遍历一次 “遍历”… 目录 1.图的遍历1.广度优先遍历2.深度优先遍历 2.最小生成树1.Kruskal算法2.Prim算法 1.图的遍历
给定一个图G和其中任意一个顶点 v 0 v_0 v0从 v 0 v_0 v0出发沿着图中各边访问图中的所有顶点且每个顶 点仅被遍历一次 “遍历”对结点进行某种操作的意思
1.广度优先遍历 **例如**现在要找东西假设有三个抽屉东西在哪个抽屉不清楚现在要将其找到广度优先遍历的做法是 先将三个抽屉打开在最外层找一遍将每个抽屉中红色的盒子打开再找一遍将红色盒子中绿色盒子打开再找一遍直到找完所有的盒子 注意每个盒子只能找一次不能重复找 思考如何防止节点被重复遍历 增加一个数组用于标记是否入过队列这样可以防止重复遍历
void BFS(const V src)
{size_t srci GetVertexIndex(src);queueint q;vectorbool visited(_vertexs.size(), false); // 标记数组q.push(srci);visited[srci] true;int levelSize 1; // 控制每层出的数量while (!q.empty()){// 一层一层出for (size_t i 0; i levelSize; i){int front q.front();q.pop();cout front : _vertexs[front] ;// 把front的邻接顶点入队列for (size_t j 0; j _vertexs.size(); j){if (_matrix[front][j] ! MAX_W visited[j] false){q.push(j);visited[j] true;}}}cout endl;levelSize q.size();}
}2.深度优先遍历 **例如**现在要找东西假设有三个抽屉东西在哪个抽屉不清楚现在要将其找到深度优先遍历的做法是 先将第一个抽屉打开在最外层找一遍将第一个抽屉中红盒子打开在红盒子中找一遍将红盒子中绿盒子打开在绿盒子中找一遍递归查找剩余的两个盒子 **深度优先遍历**将一个抽屉一次性遍历完(包括该抽屉中包含的小盒子)再去递归遍历其他盒子 如果给的图不是连通图以某个顶点为起点没有遍历完成怎么保证遍历完剩下的顶点 在visited数组中找没有遍历过的顶点再次进行遍历
void _DFS(size_t srci, vectorbool visited)
{cout srci : _vertexs[srci] endl;visited[srci] true;for (size_t i 0; i _vertexs.size(); i){if (_matrix[i] ! MAX_W visited[i] false){_DFS(i, visited);}}
}void DFS(const V src)
{size_t srci GetVertexIndex(src);vectorbool visited(_vertexs.size(), false);_DFS(srci, visited);// 处理存在不连通的情况for (size_t i 0; i _vertexs.size(); i){if (!visited[i]){_DFS(i, visited);}}
}2.最小生成树
连通图中的每一棵生成树都是原图的一个极大无环子图即 从其中删去任何一条边生成树就不在连通反之在其中引入任何一条新边都会形成一条回路 若连通图由n个顶点组成则其生成树必含n个顶点和n-1条边因此构造最小生成树的准则有三条 只能使用图中权值最小的边来构造最小生成树 最小的成本让着N个顶点连通 只能使用恰好n-1条边来连接图中的n个顶点选用的n-1条边不能构成回路 构造最小生成树的方法Kruskal算法和Prim算法这两个算法都采用了逐步求解的贪心策略贪心算法 指在问题求解时总是做出当前看起来最好的选择 即贪心算法做出的不是整体最优的的选择而是某种意义上的局部最优解 贪心算法不是对所有的问题都能得到整体最优解
1.Kruskal算法
任给一个有n个顶点的连通网络 N { V , E } N\{V,E\} N{V,E} 首先构造一个由这n个顶点组成、不含任何边的图 G { V , N U L L } G\{V,NULL\} G{V,NULL}其中每个顶点自成一个连通分量其次不断从E中取出权值最小的一条边(若有多条任取其一)若该边的两个顶点来自不同的连通分量则将此边加入到G中 如此重复直到所有顶点在同一个连通分量上为止 核心每次迭代时选出一条具有最小权值且两端点不在同一连通分量上的边加入生成树 Kruskal算法是一种全局贪心的算法 如何判断是否形成环 并查集 在下图执行Kruskal算法的过程 加了阴影的边属于不断增长的森林A该算法按照边的权重大小依次进行考虑箭头指向的边是算法每一步考察的边 如果该条边将两颗不同的树连接起来它就被加入到森林里从而完成对两棵树的合并
W Kruskal(Self minTree)
{size_t n _vertexs.size();// 初始化minTreeminTree._vertexs _vertexs;minTree._indexMap _indexMap;minTree._matrix.resize(n);for (size_t i 0; i n; i){minTree._matrix[i].resize(n, MAX_W);}priority_queueEdge, vectorEdge, greaterEdge minQueue;// 建堆排序for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (i j _matrix[i][j] ! MAX_W){minQueue.push(Edge(i, j, _matrix[i][j]));}}}// 选出n-1条边size_t size 0;W totalW W();UnionFindSet ufs(n);while (!minQueue.empty()){Edge min minQueue.top();minQueue.pop();// 判环 - 并查集if (!ufs.InSameSet(min._srci, min._dsti)){cout _vertexs[min._srci] - \ _vertexs[min._dsti] : min._w endl;minTree._AddEdge(min._srci, min._dsti, min._w);ufs.Union(min._srci, min._dsti); // 入集size;totalW min._w;}else{cout Forming Ring: ;cout _vertexs[min._srci] - \ _vertexs[min._dsti] : min._w endl;}}if (size n - 1){return totalW;}else{return W();}
}2.Prim算法
Prim算法的一个性质是集合A中的边总是构成一棵树这棵树从一个任意的根节点r开始一直长大到覆盖V中的所有结点时为止 Prim算法思路天然避环算法每一步在连续集合A和A之外的结点的所有边中选择一条轻量级边加入到A中本策略也属于贪心策略因为每一步所加入的边都必须是使树的总权重增加量最小的边 Prim算法是一种局部贪心算法 在下图执行Prim算法的过程 初始的根节点为a加阴影的边和黑色的结点都属于树A在算法的每一步树中的结点就决定了图的一个切割横跨该切割的一条轻量级边被加入到树中**例如**在途中第二步该算法可以选择将边 ( b , c ) (b, c) (b,c)加入到树中也可以将边 ( a , h ) (a, h) (a,h)加入到树中因为这两条边都是横跨该切割的轻量级边
W Prim(Self minTree, const W src)
{size_t srci GetVertexIndex(src);size_t n _vertexs.size();// 初始化minTreeminTree._vertexs _vertexs;minTree._indexMap _indexMap;minTree._matrix.resize(n);for (size_t i 0; i n; i){minTree._matrix[i].resize(n, MAX_W);}// true false表示该元素是否在该集合内vectorbool X(n, false);vectorbool Y(n, true);X[srci] true;Y[srci] false;// 从X-Y集合中连接的边里面选出最小的边priority_queueEdge, vectorEdge, greaterEdge minQueue;// 先把srci连接的边添加到队列中for (size_t i 0; i n; i){if (_matrix[srci][i] ! MAX_W){minQueue.push(Edge(srci, i, _matrix[srci][i]));}}size_t size 0;W totalW W();while (!minQueue.empty()){Edge min minQueue.top();minQueue.pop();// 最小边的目标也在X集合则构成环if (X[min._dsti]){cout Forming Ring:;cout _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;}else{cout _vertexs[min._srci] - _vertexs[min._dsti] : min._w endl;minTree._AddEdge(min._srci, min._dsti, min._w);X[min._dsti] true;Y[min._dsti] false;size;totalW min._w;// 可能最小生成树已经生成但是多了很多成环边无须继续遍历if (size n - 1){break;}// 将目标顶点连接的边加入到队列中for (size_t i 0; i n; i){if (_matrix[min._dsti][i] ! MAX_W Y[i]){minQueue.push(Edge(min._dsti, i, _matrix[min._dsti][i]));}}}}// 实际不一定存在最小生成树if (size n - 1){return totalW;}else{return W();}
}
