带权图最小生成树prim的优化一、优化内容在prim算法中，使用while循环对每一个节点进行遍历，其中对边进行出堆操作进行了E遍，堆邻边进行遍历为E遍，总体来说prim的时间复杂度为:O(ElogE)。在prim中会对每一条边加入堆中，但取出时，取出的边有可能不再是横切边；那么我们现在要维护一个数据结构用来存储和邻节点连接最短的横切边，在不断的扩大红色节点
......
477
0
0
2022-04-18
最小生成树之prim算法一、prim算法最小生成树prim版，是由prim提出的在prim的实现中，需要使用辅助数据结构——最小堆，将所有的横切边放入最小堆中，经过一系列操作后取堆顶元素，就可得到最小生成树。其思想是基于切分定理，其过程如下：如下图，初始时，全为蓝色，当某个节点被访问到时，就将其标记(实现中用marked数组标记，标记后即为红色）：从0开始:
......
372
0
0
2022-04-18
图的最小生成树(Minimum Span Tree)一、介绍最小生成树：指在一张有V个节点和V-1条边的图中，V-1条边连接V个节点，所有边的权值之和最小，所形成的树。如下图：红色的边和所有节点相连所形成的一颗树，就是最小生成树适用范围：带权无向图通常为连通图(如果有多个不连通的图，则每个子图的最小生成树之和就为最小生成树森林)二、实际应用最小生成树广泛应用
......
431
0
0
2022-04-18
带权图的表示一、介绍带权图(Weighted Graph)：带权图就是指图中的每一条边都有对应的一个或一组值，通常情况下这个值的是数值。如：在交通运输网中，边上的权值可能表示的是路程，也可能表示的是运输费用（显然二者都是数字）。不过，边上的权值也有可能是其它东西，比如说是一个字符串，甚至是一个更加复杂的数据包，里面集合了更多的数据。二、表示方法邻接表在无权图
......
403
0
0
2022-04-18
图的广度优先遍历一、介绍广度优先遍历广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,…,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。分为三个步骤：使用一个辅助队列，首先将第一个节点v放入队列，并标记也被
......
465
0
0
2022-04-18
基于深度优先遍历的寻路算法一、介绍寻路算法是用来获取两节点之间的路劲问题，它是基于图的深度优先遍历而来的，在图的遍历过程中，每当遍历到一个节点是，会使用一个from数组用来记录该节点的上一个节点，与此同时我们会使用一个栈(先进后出），将from数组记录的节点依次放入栈中，然后依次再从栈中取出栈顶元素将其放入一个队列中，最后对队列中元素依次索引出就可得到相应节
......
364
0
0
2022-04-17
图的深度优先遍历及联通分量一、介绍深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。联通分量，无向图 G 的一个极大连通子图称为 G 的一个连通分量（或连通分支）。连通图只有一个连通分量
......
354
0
0
2022-04-17
图的读取算法一、图的读取在这小节中我们将会学习到啊这样将文件读如图中，前面我们学了稠密图和稀疏图，为了统一接口我们使用模板类，让其同时具备读入两种图的能力。代码实现#include <iostream>
#include <string>
#include <fstream>
#include <sstream
......
370
0
0
2022-04-17
图的相邻节点迭代器 ( adjIterato )一、介绍迭代器是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素,每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口,所谓迭代器是一种概念上的抽象:那些行为上像迭代器的东西都可以叫做迭代器。用迭代器可以很大程度上隔离容器底层实现，使用时只需依赖迭代器相对统一的方法/接口。图的相邻节点迭代器
......
362
0
0
2022-04-17
图论(Graph Theory)一、介绍图是用来对对象之间的成对关系建模的数学结构，由”节点”或”顶点”(Vertex）以及连接这些顶点的”边”（Edge）组成。值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。二、图的分类图分为：无向图和有向图(无向图是有向图的特殊形式)无
......
590
0
0
2022-04-17
并查集的路径压缩一、介绍并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。通俗的说就是把find过程中“查找节
......
284
0
0
2022-04-17
并查集基于rank的优化一、介绍背景前面将到并查集基于size的优化，其实仔细想想，还是有可以优化的地方；size[i]是指以i为根节点树的节点数；是将节点数量多的树的根节点向节点数好的树的根节点连接，在一般情况下是得到了优化，但是这里就存在问题了，当出现：节点数多的树它的高度非常高的时候，size的优化方式就不太高效了。rankrank[i]:是用来记录以
......
409
0
0
2022-04-17
并查集基于size的优化一、介绍及逻辑介绍在上一小节我们使用指针的方法将每一个元素都看作是一个节点，并且是节点指向另一个节点(包括自己)，在这一小节中我们将在此基础上进行优化。先来介绍一下什么是”size”size : size[i] 是指用来记录以i为根节点的树所包含的节点个数，本质是一个数组逻辑先来看看下面的图片：现在需要将4，2连接起来，该怎么连？方法
......
287
0
0
2022-04-16
并查集的另一种实现思路(优化)一、介绍在并查集的Union( ) 中使用指针，将每一个元素看作是一个节点，并将每一个节点都指向一个节点(可以是其他节点或节点本身)即Quick Union；使用这种方法在后续可以更好的对并查集进行优化。二、 Union的表示方法及逻辑在Quick Find下的union时间复杂度为( O(n) )将每一个元素看作是一个节点，如
......
273
0
0
2022-04-16
并查集基础一、概念及其介绍并查集是一种树型结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。对于并查集主要支持两个操作：并{ union(p,q) }查找{ find(p) }来回答一个问题：连接{ inConnected
......
411
0
0
2022-04-16