算法(1) MST - 最小生成树

时间:2022-09-20 09:53:09

最小生成树

@(算法)

概念

生成树:

如果连通网G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。

最小生成树:

在连通网G的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。

算法(1) MST - 最小生成树

Kruskal 算法

又称为加边法,将边排序后从小到大依次检查直到所有边都得到联通。这个方法因为只与边有关,所以适合点稠密图。
算法(1) MST - 最小生成树

输入

点集合vextex, 边集合edge

算法步骤

  1. 将所有边按代价值从小到大排序,并初始化一个空点集A以及一个空边集B。
  2. 依次遍历所有边,若当前边中存在一个点不属于A,那么则将该边加入B,并将边的两点加入A;若当前边的两点都已加入A中,则跳过该边。
  3. 按2的做法,直到A=vextex结束。

Prim 算法

又称为加点法,任取一点后,通过这个点逐渐长出整个生成树,因为操作都和点相关,所以适合边稠密图。

输入

点集合vextex, 边集合edge

算法步骤

  1. 从vextex中任取一点u,并设置两个点集合, U = u , V = v e x t e x u ,U表示已经成为最小生成树一部分的点集。
  2. 设置一个visited数组,用于表示哪些点已经加入到U当中(在python里我是用字典实现的,所以不需要这个数组),同时再设置一个cost数组,用于表示当前点连接到U上的代价。
  3. 通过U里面的点,先更新所有V里的点直接连接U里的点的代价,并记录到cost数组,cost数组索引是V里面的点。然后选出所有连接两个点集的边中最小的边,把V里对应的点加入到U里。
  4. 判断U的大小是否等于vextex,若等于则结束算法,若不等于则重新执行3.

代码实现

# coding:utf-8

from functools import cmp_to_key
import numpy as np


class Edge:
    def __init__(self, cost=0., u='', v=''):
        self.cost = cost
        self.u = u
        self.v = v


def get_vextex_and_edge(n, m):
    vextex = ['' for i in range(n)]
    edge = [Edge() for i in range(m)]
    return vextex, edge


def kruskal(vextex: list, edge: list):
    vset = []

    def cmp(a, b):
        return a.cost - b.cost

    edge = sorted(edge, key=cmp)
    for e in edge:
        u, v = vextex.count(e.u), vextex.count(e.v)
        if u and v: continue
        if u: vset.append(u)
        if v: vset.append(v)
        if len(vset) == len(vextex):
            break
    return edge


def prim(vextex: list, edge: list):
    n = len(vextex)
    visited = [0 for i in range(n)]
    cost = [np.inf for i in range(n)]

    uset = [vextex[0]]
    visited[0], cost[0] = 1, 0

    new_edge = {}
    for i in range(len(edge)):
        val = new_edge.get(edge[i].u, default=[])
        new_edge[edge[i].u] = val.append((edge.v, edge.cost))
    edge = []
    for i in range(n):
        for g in range(len(new_edge[vextex[i]])):
            cost[g[0]] = min(cost[g[0]], g[1])
        chosed = min(new_edge[vextex[i]], key=lambda x: x[1])
        uset.append(chosed[0])
        edge.append(Edge(u=vextex[i], v=chosed[0], cost=chosed[1]))
        if len(uset) == n:
            break
    return edge


if __name__ == '__main__':
    vextex, edge = get_vextex_and_edge(n=0, m=0)
    kruskal(vextex, edge)
    prim(vextex, edge)


补充

1.图:
由顶点集 V (vertices)和边集 E (edges)组成,表示为 G = ( V , E ) ,顶点 v V ,边 e E

2.连通图:
在无向图中,若任意两个顶点 v i v j 都有路径相通,则称该无向图为连通图。

3.强连通图:
在有向图中,若任意两个顶点 v i v j 都有路径相通,则称该有向图为强连通图。

4.连通网:
在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为;权代表着连接连个顶点的代价,称这种连通图叫做连通网。

5.树: