Prime算法解决的也是最小生成树的问题，思路很直观，开始时，任意选择一个点作为根，然后选择离这个点最近的一个点和它连通，组成一个新的连通分量，再用新选的点更新其他未被选择的点到已知连通分量的距离，更新完毕之后，选择一个离已知连通分量最近的点和已知连通分量连通，组成新的连通分量，重复这个过程。直到所有点都被选中。   Prime算法和Dijstra算法很像，不同点在于Prime更新的是从已知连通分量到其他各个顶点的距离，Dijstra更新的是从源点到其他各个顶点的距离。//表示边 struct Edge { int u;//起点 int v;//终点 int w;//权重 }; class Prime { vector<int> dis; vector<bool> book; public: int minimumSpanningTreeSum(vector<Edge> &edges,int n) {

Kruskal算法是解决最小生成树问题的一种算法。其算法过程是一开始，所有点都是孤立的点。对所有的边从小到大排序每次选取权值最小且其两个顶点还不连通的边连通选取的边的两个顶点重复这个过程，直到所有的顶点连通问题：什么时候停止循环? 答案：选取了n-1条边问题：为什么是n-1条边？选取了n-1条边就保证n个顶点连通了?答案：n个顶点连通，且不构成回路，需要n-1条边。那存在n-1条边，并且不构成回路，那么通过这n-1条边，n个顶点就是连通的。在Kruskal算法中，每次选取一条权值最小边且其两个顶点还不连通，每次选一条边，有三种情况：一是两个顶点自成一派，都是孤立的点，二是一个顶点在已知连通分量里，另一个顶点是孤立的点，三是两个顶点在两个未连通的已知连通分量里，第一种情况的两个顶点连通后，成为单独的连通分量，这种情况增加一条边，增加两个顶点。第二种情况的两个顶点连通后，已知连通分量增加一个顶点，这种情况增加一条边，增加一个顶点。第三种情况的两个顶点连通后，两个未连通的已知连通分量连通了，这种情况增加一条边，顶点的个数不变。问题是选取n-1条这样的边，为什么n个顶点就都连通了?。如果n个顶

并查集算法主要由两个方法构成：查、并。用于具有连通性的数据结构，比如图，亲戚的亲戚还是亲戚，同伙的同伙还是同伙，同事的同事也是同事。某一写字楼下的快餐店里，A与B在一张桌子吃饭，如果问A与B是不是同事，看看A与B的老板是不是同一人，如果是就是同事，如果不是，就不是。假设目前A与B的老板不是同一人，两个月后，A的公司收购了B的公司，B和A成为了同事，这就是并，合并。假设数组arr，长度为n+1，目前有n个员工，编号分别为1～n，一开始他们一个人是一个公司，各自为政，自己是自己的老板。然后经过一段时间的公司合并，老板的个数减少了。员工的个数增加了。这会儿任意给定两个员工，他们是不是同事?代码如下:class UnionFindSets { vector<int> boss; public: UnionFindSets(int n) { boss.emplace_back(0); for(int i = 1;i <= n;i++) { boss.emplace_back(i);

一、定义： 所有的父节点都小于子节点的完全二叉树。叫做小根堆。二、性质：节点个数为N的小根堆，其高度为logN。N/2之后的节点都是叶子结点。第i个节点的左儿子的序号是ix2,右儿子的序号是ix2+1，父亲节点的序号为i/2三、如何存储? 用一维数组存储。申请一个长度为N+1的数组，四、建堆的两种方式：直接用一个数组存储数，然后，从后往前依次调整数的位置，使以当前位置为根的二叉树为小根堆直到数组的第一个数。插入法，依次读入每个数，把它插入小根堆，并调整位置，使插入数后二叉树继续保持为小根堆方式一代码 文末代码中create1方法 方式二代码 文末代码中create2方法五、排序时间复杂度为 NlogN 文末代码中heapSort方法六、从堆顶删除一个数? 文末代码中deleteMin方法七、增加一个数? 文末代码中addOneNum方法class SmallPriorityQueue { vector<int> h; int N; public: SmallPriorityQueue(vector<int> & arr,

之前安装matomo，遗留一个小问题，就是访问博客的时候，浏览器会显示不安全字样。因为是直接ip安装的matomo，所以会这样。这次给matomo弄了个二级域名，并且配置了https，可以直接通过二级域名访问matomo后台。博客里的追踪代码也是用的二级域名。就不会显示不安全字样了。配置域名的过程中，遇到个问题，就是域名、证书、nginx等配置完毕之后，访问二级域名，会直接下载index.php文件，而不是显示页面。后面解决了，原来是matomo监听的端口也是80，和typecho冲突了。修改nginx配置把监听端口改了一个其他的，再在云服务商那里修改防火墙规则，加上新端口访问规则。就可以正常访问了。