实现常用数据结构(图)——图的算法

最小生成树

图的生成树是包含图的所有点和部分边的一个图, 它是图的一个子集. 之所以叫树, 是因为生成树中没有环.

最小生成树是生成树中权值最小的一棵树.

Prim 算法

由一个顶点开始, 每次选择与已有点顶点相连但不指向已有顶点但最小边, 然后将边和指向的订单并入到树中. 直到没有可以选择的边为止.

以下是 Python 代码:

[Note]: 由于此算法对存储结构无要求, 故抽象化了一个数据结构来保存当前对图. 以下代码中使用了函数 get_lines(node) , 它是一个生成器函数, 生成器每次返回 node 引申出的路径权值和目标节点.

def prim(target) -> int:
    low_cost = [float('inf')] * target.size  # 可以到达每个顶点的最小路径长度, 初始为无穷大
    v = set()  # 顶点集合, 每添加一个顶点就加入其中
    v.add(0)  # 从0号顶点开始生成树
    res = 0  # 最小生成树的权值
    for line_cost, target_node in target.get_lines(0):  # 查找有关0顶点的所有边, 获得路径长度和目标节点
        if low_cost[target_node] > line_cost:  # 如果能够获得更短的路径, 就更新 low_cost
            low_cost[target_node] = line_cost

    for _ in range(target.size - 1):  # 由于0号节点已经在集合中, 所以遍历次数少一次
        min_line, min_node = float('inf'), 0
        for i, cost in enumerate(low_cost):
            if cost < min_line:
                min_line, min_node = cost, i

        v.add(min_node)  # 将当前边最小的目标顶点加入顶点集合中
        res += min_line  # 生成树的权值更新
        low_cost[min_node] = float('inf')  # 将加入顶点集合的顶点的low_cost更新为无穷大

        for line_cost, target_node in target.find(min_node):  # 根据加入的顶点有关的边更新low_cost
            if target_node not in v and low_cost[target_node] > line_cost:
                low_cost[target_node] = line_cost
    return res

Kruskal 算法

依次按大小将所有的边并入到集合中, 如果形成了环则跳过当前边, 直到所有点都并入到并入到树中为止.

要判断是否形成了环只需要引入并查集, 如果一条边的两个点属于同一个集合, 则会形成环 .

并查集的代码不多做赘述, 具体请看 并查集

以下是 Python 代码:

[Note]: 由于此算法对存储结构无要求, 故抽象化了一个数据结构来保存当前对图. 以下代码中使用了函数 target.all_lines(), 它返回了一个 字典列表 , 列表中每个元素分别为: pre_node, target_node, cost, 其中分别表示了起始点, 终点和路径长度.

def kruskal(target) -> int:
    uf = UnionFind(range(target.size))
    v = set()
    res = 0
    line_list = sorted(target.all_lines(), key=lambda x: x[cost])
    for node1, node2, line_cost in line_list:
        if len(v) == target.size:
            break
        if not uf.union(node1, node2):
            res += line_cost
            v.add(node1)
            v.add(node2)
    return res

最短路径

Dijkstra 算法

Dijkstra 算法是用来求得某一点到图中所有点的最点距离的算法, 其与 Prim 算法有相似之处, 都是寻找可以到达的边, 然后用一个数组记录其最小值. 只不过 Dijkstra 算法在每次取最小值时, 记录的值都是起始点到当前点的距离.

以下是 Python 代码:

[Note]: 由于此算法对存储结构无要求, 故抽象化了一个数据结构来保存当前对图. 以下代码中使用了函数 get_lines(node) , 它是一个生成器函数, 生成器每次返回 node 引申出的路径权值和目标节点.

def dijkstra(target_map: Map, node: int):
    point_dict = {node: 0}  # 表示起始点到目标点的最小路径长度
    pre_node = {node: node}  # 记录路径中的前驱
    v = {node}  # 记录节点是否已经有了最短路径

    for line_node, line_cost in target_map.get_lines(node):  # 先将起始点能直接遍历到的点记入dict中
        point_dict[line_node] = line_cost
        pre_node[line_node] = node

    for _ in range(target_map.size - 1):
        cost, min_node = float('inf'), None  # 寻找当前最小路径的点
        for index_node in point_dict:
            if index_node not in v and cost > point_dict[index_node]:
                cost = point_dict[index_node]
                min_node = index_node

        v.add(min_node)

        for line_node, line_cost in target_map.get_lines(min_node):  # 更新dict
            if line_node not in point_dict or point_dict[line_node] > line_cost + cost:
                point_dict[line_node] = line_cost + cost
                pre_node[line_node] = min_node

    return format_res(point_dict, pre_node)


def format_res(cost, pre):
    res_dict = {}
    for node in cost:
        res_dict[node] = {'cost': cost[node]}
        path = [str(node)]
        idx = node
        while pre[idx] != idx:
            idx = pre[idx]
            path.append(str(idx))
        res_dict[node]['path'] = '->'.join(path[::-1])
    return res_dict

Floyd 算法

Floyd 算法就是不断查找在两条路径之间是否有更短的路径, 然后更新一个二维数组的过程的算法.

以下是 Python 代码:

[Note]: 由于此算法对存储结构无要求, 故抽象化了一个数据结构来保存当前对图. 以下代码中使用了函数 get_cost(i, j) , 它返回了两个点之间的边的长度, 如果两点之间没有边 , 则返回无穷大.

def floyd(target_map) -> (dict, dict):
    _dict = {i: {} for i in range(target_map.size)}
    path = {i: {} for i in range(target_map.size)}
    for i in range(target_map.size):
        for j in range(target_map.size):
            if i == j:
                _dict[i][j] = 0
            else:
                _dict[i][j] = target_map.get_cost(i, j)

    for v in range(target_map.size):
        for i in range(target_map.size):
            for j in range(target_map.size):
                if i != v and j != v and i != j and _dict[i][j] > _dict[i][v] + _dict[v][j]:
                    _dict[i][j] = _dict[i][v] + _dict[v][j]
                    path[i][j] = v
    return _dict, path