关于最小生成树以及Prim算法参考上一篇:最小生成树MST 之 Prim及其实现

Kruskal算法

Kruskal算法实际上是 贪心+并查集,贪心用来查找权值最小的边,并查集来检测顶点的连通性(关于并查集不再详述)。

不同于Prim算法,Kruskal不是面向顶点来生成MST的,Kruskal只考察边集,只看当前最小权值的边,所以需要并查集来检测顶点连通的状态(Prim通过已连通的顶点来选择权值最小的边,而Kruskal先去掉所有的点,在总边集中找最小的边)。

Kruskal算法的步骤:

  1. 将边集内的边按权值大小升序排序。
  2. 依次考察每条边,如果边的两顶点不同源(至少有一点未被访问),则将此边纳入生成树。
  3. 执行步骤2,直到每一个点都被访问。

从步骤中可以看出,Kruskal的性能取决于排序算法,需要选择合适的排序算法。

Kruskal的实现(Python)

  • 随机生成5×5-9×9的图(邻接矩阵)
  • 排序使用python自带的sorted()方法
  • 输出访问顺序和总开销
import random, time
father = []
MAX_DISTANCE = 100  # 边的最大权值


def create_map():  # 生成图(邻接矩阵)
    map = []
    size = random.randint(5, 9)
    print("图大小:", size)
    
    for i in range(size):
        row = []
        for j in range(size):
            row.append(random.randint(1, MAX_DISTANCE))
        map.append(row)
    
    print("生成图:")
    for i in range(size):
        print(map[i])
    
    return map


def get_edges(map):
    edges = []
    for i in range(len(map)):
        for j in range(len(map)):
            edges.append([i, j, map[i][j]])
    return len(map), len(edges), edges


def find(n):  # 查找顶点的父亲顶点
    if father[n] == n:
        return n
    father[n] = find(father[n])
    return father[n]


def union(map_size, edge_size, edges):
    global father
    father = [i for i in range(map_size)]  # 并查集,初始情况下顶点的源点为自身
    tol_distance = 0  # 总开销
    visit_order = []  # 记录访问顺序
    
    for i in range(edge_size):
        node1 = find(edges[i][0])  # 边的一个顶点的源点
        node2 = find(edges[i][1])  # 边的令一个顶点的源点
        if node1 != node2:  # 不同源
            visit_order.append(edges[i])
            tol_distance += edges[i][2]
            father[node2] = node1  # 合并,将两顶点的源点合并为一个
            
    return visit_order, tol_distance
    

def kruskal(map_size, edge_size, edges):
    edges = sorted(edges, key=lambda x: x[2])  # 对边进行权值的升序排序
    return union(map_size, edge_size, edges)


def main():
    map_size, edge_size, edges = get_edges(create_map())
    visit_order, tol_distance = kruskal(map_size, edge_size, edges)

    print("访问顺序:[顶点, 顶点, 权值]")
    for each in visit_order:
        print(each)

    print("总开销:", tol_distance)

    
if __name__ == "__main__":
    main()

Continue reading “最小生成树MST 之 Kruskal及其实现”

昨天突然想不起来并查集的名字,忽觉忘记的有点多,于是决定复习一下各种算法。

问题引入

要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

将城市抽象为点,光缆抽象为边,费用抽象为权值,就可以绘制一幅连通加权无向图

类似的还有修路,建桥等问题,抽象出来都属于最小生成树。

最小生成树简介

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即 {\displaystyle (u,v)\in E}),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即 {\displaystyle T\subseteq E})且 (V, T) 为树,使得

的 w(T) 最小,则此 T 为 G 的最小生成树

最小生成树其实是最小权重生成树的简称。

一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树,它们的并被称为最小生成森林

以有线电视电缆的架设为例,若只能沿着街道布线,则以街道为边,而路口为顶点,其中必然有一最小生成树能使布线成本最低

来自 最小生成树 – 维基百科

Prim算法

与之齐名的还有Kruskal算法,相比之下,Prim是从图中的顶点出发,而Kruskal更注重图中的边。

不管是Prim还是Kruskal,其核心都是贪心——寻找当前状态下最小权值的边。

算法步骤:

  1. 从一个顶点出发。
  2. 查找与已连接顶点相连的边权值最小的边。
  3. 通过此边连接对应顶点。
  4. 重复2、3步骤,直到连接所有顶点。

Continue reading “最小生成树MST 之 Prim及其实现”

Merkle Tree简介

Merkle Tree实际上就是 树+Hash,具有树的性质,树的每个节点都是Hash值。Merkle Tree有以下特点:

  1. Merkle Tree可以是二叉树,也可以是多叉树,不管是什么树,它都具有树结构的所有特点。
  2. Merkel Tree的叶子节点的Value是数据集合的单元数据 或 单元数据的Hash值。
  3. Merkel Tree所有非叶子节点的Value是所有子节点Value的Hash值。

Merkle Tree的应用

Merkel Tree多用在数据验证,其中最有名的应用领域可能就属加密货币了。矿机在挖矿实际上就是在运算一组复杂的公式:

SHA256(SHA256(version + prevHash + merkleRoot + time + currentDifficulty + nonce )) < TARGET

这里不必深究公式的意义,只需要关注其中的一个“merkleRoot”参数,这个“merkleRoot”就是Merkle Tree的根节点的值。想要算出根节点的值,必须要从叶子节点出发(在加密货币中,叶子节点通常为各区块内从n个交易提取的n个Hash值),最后由根节点的两个子节点的Hash计算出根节点的Hash。这只是挖矿的一个小环节。

Merkle Tree的实现

Continue reading “Merkle Tree及其实现”