算法89---图的最小生成树

一、Prim算法实现

思路：

1、一个存储最小树的边列表mst、一个存储最小树的点集合used、一个堆，排序最小树边缘的最小边。堆顶为最小值。

2、建立邻接表，如{'A':[(7,'A','B'),(5,'A','D')]}

3、随机选初始点

4、排序初始点的边权重，建立堆

代码：

from heapq import heapify, heappop, heappush
from collections import defaultdict


def prim(nodes, edges):
    #######conn是邻接表，字典形式
    conn = defaultdict(list)
    ####建立邻接表，如{'A':[(7,'A','B'),(5,'A','D')]}
    for n1, n2, c in edges:
        conn[n1].append((c, n1, n2))
        conn[n2].append((c, n2, n1))

    ##### mst就是存边结果，[('A','D',5)……]
    mst = []
    ##### used就是存已经放进mst中的点，
    used = set(nodes[0])
    ##### usable_edges 为建立好的树（采用堆排序建立的树）
    usable_edges = conn[nodes[0]][:]
    #####堆排序，保证堆顶的边权重为最小。
    heapify(usable_edges)

    ##### 堆中弹出的点为最后加入的点，其连接的其他边如果不在used里，则加入堆中
    while usable_edges:
        cost, n1, n2 = heappop(usable_edges)
        if n2 not in used:
            used.add(n2)
            mst.append((n1, n2, cost))
            ####conn最后加入的点的其他边的也加入堆中
            for e in conn[n2]:
                if e[2] not in used:
                    heappush(usable_edges, e)
    return mst


nodes = list("ABCDEFG")
edges = [("A", "B", 7), ("A", "D", 5),
         ("B", "C", 8), ("B", "D", 9),
         ("B", "E", 7), ("C", "E", 5),
         ("D", "E", 15), ("D", "F", 6),
         ("E", "F", 8), ("E", "G", 9),
         ("F", "G", 11)]
print ("prim:", prim(nodes, edges))

二、村庄造路问题：

题目：已知m个奇、偶数为0或1，arr(i,j)为i到j的代价，则需要知道所有数的最小代价是多少?

如：

input：m = 4, arr = [[2,1,3],[2,1],[3]]

output:最小代价 = 4

############################

思路：图的最小生成树 ，新建一个起始点，然后建立无向图，找到最小生成树，输出最小生成树的价值和即可。

代码：

　

from collections import defaultdict
from heapq import heapify, heappush, heappop
import sys


def prim(m, arr):
    if len(arr) == 0 or len(arr[0]) == 0:
        return 0
    nodes = [i for i in range(m)]
    graph = defaultdict(list)
    res = 0
    for i in range(len(arr)):
        for j in range(1,len(arr[i])):
            graph[i].append([arr[i][j], i, i + j + 1])

    use_node = set([nodes[0]])
    heap_node = graph[0]
    heapify(heap_node)
    while heap_node:
        val, u, v = heappop(heap_node)
        if v not in use_node:
            use_node.add(v)
            res += val
            for e in graph[v]:
                if e[2] not in use_node:
                    heappush(heap_node, e)
    return res


m = 3
arr = [[2, 1, 3], [2, 1], [3]]
# arr = [[1,2,2],[1,2],[1]]
print(prim(m, arr))

三、360春招2019笔试题——三角形优化

题目：

题目：已知m个奇、偶数为0或1，arr(i,j)为i到j的代价，则需要知道所有数的最小代价是多少?
如：
input：m = 4,
    arr = [[2,1,3],[2,1],[3]]
output:最小代价 = 4

思路：

图的最小生成树 把除了每一行的第一个数，用别的值建立无向图，找到最小生成树，再加上每一行第一个数的最小值即可。

代码：

from collections import defaultdict
from heapq import heapify, heappush, heappop
import sys


def prim(m, arr):
    if len(arr) == 0 or len(arr[0]) == 0:
        return 0
    nodes = [i for i in range(m)]
    graph = defaultdict(list)
    res = 0
    for i in range(len(arr)):
        for j in range(1,len(arr[i])):
            graph[i].append([arr[i][j], i, i + j + 1])

    use_node = set([nodes[0]])
    heap_node = graph[0]
    heapify(heap_node)
    while heap_node:
        val, u, v = heappop(heap_node)
        if v not in use_node:
            use_node.add(v)
            res += val
            for e in graph[v]:
                if e[2] not in use_node:
                    heappush(heap_node, e)
    return res


m = 3
arr = [[2, 1, 3], [2, 1], [3]]
# arr = [[1,2,2],[1,2],[1]]
print(prim(m, arr))

四、克鲁斯卡尔算法

代码：

class DisjointSet(dict):
    '''不相交集'''

    def __init__(self, dict):
        pass

    def add(self, item):
        self[item] = item

    def find(self, item):
        if self[item] != item:
            self[item] = self.find(self[item])
        return self[item]

    def unionset(self, item1, item2):
        self[item2] = self[item1]


def Kruskal_1(nodes, edges):
    '''基于不相交集实现Kruskal算法'''
    forest = DisjointSet(nodes)
    MST = []
    for item in nodes:
        print(item)
        forest.add(item)
    edges = sorted(edges, key=lambda element: element[2])
    num_sides = len(nodes)-1  # 最小生成树的边数等于顶点数减一
    for e in edges:
        node1, node2, _ = e
        parent1 = forest.find(node1)
        parent2 = forest.find(node2)
        if parent1 != parent2:
            MST.append(e)
            num_sides -= 1
            if num_sides == 0:
                return MST
            else:
                forest.unionset(parent1, parent2)
    pass


def Kruskal(nodes, edges):
    ''' Kruskal 无向图生成最小生成树 '''
    all_nodes = nodes  # set(nodes)
    used_nodes = set()
    MST = []
    edges = sorted(edges, key=lambda element: element[2], reverse=True)
    # 对所有的边按权重升序排列
    while used_nodes != all_nodes and edges:
        element = edges.pop(-1)
        if element[0] in used_nodes and element[1] in used_nodes:
            continue
        MST.append(element)
        used_nodes.update(element[:2])
        # print(used_nodes)
    return MST


def main():
    nodes = set(list('ABCDEFGHI'))
    edges = [("A", "B", 4), ("A", "H", 8),
             ("B", "C", 8), ("B", "H", 11),
             ("C", "D", 7), ("C", "F", 4),
             ("C", "I", 2), ("D", "E", 9),
             ("D", "F", 14), ("E", "F", 10),
             ("F", "G", 2), ("G", "H", 1),
             ("G", "I", 6), ("H", "I", 7)]
    print("The undirected graph is :", edges)
    print("The minimum spanning tree by Kruskal is : ")
    print(Kruskal_1(nodes, edges))


if __name__ == '__main__':
    main()