图在遍历的过程中，若加上一个条件：要求遍历过的顶点间路径权重和最小，这样遍历的结果，就为该图的最小生成树。

普利姆算法（Prim）

思路

• 准备：

  • 需要一个数组，用于记录访问过的点。
  • 遍历矩阵：可由邻接矩阵得到，代表目前遍历的范围

• 过程：

1. 在遍历矩阵中，从某个点出发，找出当前矩阵中权值最小的点，
2. 若不存在数组中，对该点进行如下操作：
   a. 将该点的索引添加到数组中。
   b. 设点对应的索引为，点对应的索引为；将权重矩阵（邻接矩阵）中，第行列和第行列的值设置为最大，下一轮遍历时不再考虑。
3. 将所对应的行添加到遍历矩阵中，重复1操作，直到的长度与图顶点的数量相等。

总结：

1. 循环直到所有点都在中为止；第二层循环和第三层循环：找出遍历矩阵中的最小的权重。
2. 第一步的过程中，与普通遍历不同的是：已完成的点（存放于中的点），下一轮遍历过程中仍然要遍历，因为图中某个点可能很牛逼，它所连接的点的权重都非常小。

实现

邻接矩阵

class adjacencyMatrix(object):
    def __init__(self, nodeNum, edgeNum):
        # 存储邻接矩阵中节点的个数
        self.nodeNum = nodeNum
        # 存储邻接矩阵中节点边的数量
        self.edgeNum = edgeNum
        # 在遍历时检查节点是够被使用过
        self.visited = None
        # 记录每个节点实际对应的名字
        self.nodeNameList = ['v'+str(_) for _ in range(nodeNum)]
        # 记录每个节点下标
        self.NodeList = []
        # 记录每条边的下标，（定位权重用的）
        self.EdgeList = []
        for i in range(nodeNum):
            self.EdgeList.append([NULLFLAG] * edgeNum)

    '''
    使用邻接矩阵创建图的时候，其实就是构造一个长宽均为节点数量的正方形。
    行和列的交汇点代表边的权重
    通过 头结点和尾节点的下标，可以定位连接边的权重值。
    '''
    def createGraph(self, prevIndex, weight, nextIndex):
        if prevIndex not in self.NodeList:
            self.NodeList.append(prevIndex)
            self.EdgeList[prevIndex][prevIndex] = 0
        if nextIndex not in self.NodeList:
            self.NodeList.append(nextIndex)
            self.EdgeList[nextIndex][nextIndex] = 0
        self.EdgeList[prevIndex][nextIndex] = weight
        self.EdgeList[nextIndex][prevIndex] = weight

    '''
    普利姆算法：在各种顶点之间跳来跳去，就是为了找到最小的权重值
    '''
    def primMinTree(self):
        weightList = {
            0: self.EdgeList[0]
        }
        primTree = [0]

        while len(primTree) < self.nodeNum:

            minEndNodeIndex = 0
            minStartNodeIndex = 0
            minFlag = NULLFLAG
            for i in weightList.keys():
                for j in range(self.nodeNum):
                    if minFlag > weightList[i][j] and weightList[i][j] != NULLFLAG and j not in primTree:
                        minFlag = weightList[i][j]
                        minStartNodeIndex = i
                        minEndNodeIndex = j
            primTree.append(minEndNodeIndex)
            print(minStartNodeIndex, '-', minFlag, '->', minEndNodeIndex)
            weightList[minEndNodeIndex] = self.EdgeList[minEndNodeIndex]
            weightList[minStartNodeIndex][minEndNodeIndex] = NULLFLAG
            weightList[minEndNodeIndex][minStartNodeIndex] = NULLFLAG

        return primTree

克鲁斯卡尔算法（Kruskal）

普利姆算法（Prim）是以边为基础实现的，而克鲁斯卡尔算法（Kruskal）则是在顶点的基础上做手脚。

思路

• 准备：

  • 需要一个数组，用于记录访问过的点。
  • 需要一个记录祖先节点的数组，用于判断生成的树中是否存在环路，也是一个点能否添加到中的判断条件。

• 过程：

1. 先把矩阵中所有的连接边按照权重（权值无限大除外）从小到大排序。
2. 遍历所有权值边，在中寻找每一条权值边两个对应点的祖先节点，若有相同的祖先，则说明该点可以通过其他路径到达；若无，则添加到中。

实现

邻接矩阵

class adjacencyMatrix(object):
    def __init__(self, nodeNum, edgeNum):
        # 存储邻接矩阵中节点的个数
        self.nodeNum = nodeNum
        # 存储邻接矩阵中节点边的数量
        self.edgeNum = edgeNum
        # 在遍历时检查节点是够被使用过
        self.visited = None
        # 记录每个节点实际对应的名字
        self.nodeNameList = ['v'+str(_) for _ in range(nodeNum)]
        # 记录每个节点下标
        self.NodeList = []
        # 记录每条边的下标，（定位权重用的）
        self.EdgeList = []
        for i in range(nodeNum):
            self.EdgeList.append([NULLFLAG] * edgeNum)

    '''
    使用邻接矩阵创建图的时候，其实就是构造一个长宽均为节点数量的正方形。
    行和列的交汇点代表边的权重
    通过 头结点和尾节点的下标，可以定位连接边的权重值。
    '''
    def createGraph(self, prevIndex, weight, nextIndex):
        if prevIndex not in self.NodeList:
            self.NodeList.append(prevIndex)
            self.EdgeList[prevIndex][prevIndex] = NULLFLAG
        if nextIndex not in self.NodeList:
            self.NodeList.append(nextIndex)
            self.EdgeList[nextIndex][nextIndex] = NULLFLAG
        self.EdgeList[prevIndex][nextIndex] = weight
        self.EdgeList[nextIndex][prevIndex] = weight


    def kruskalMinTree(self):
        def findParent(daddyArray, key):
            while key in daddyArray:
                key = daddyArray[key]
            return key
        daddyArray = {}
        sortArray = []
        for i in range(self.nodeNum):
            for j in range(i, self.nodeNum):
                if self.EdgeList[i][j] != NULLFLAG:
                    sortArray.append([i, j, self.EdgeList[i][j]])

        sortArray = QSort(sortArray)
        for i in sortArray:
            m = findParent(daddyArray, i[0])
            n = findParent(daddyArray, i[1])
            if m != n:
                daddyArray[m] = n
                print(i[0], '-', i[2], '->', i[1])

测试

if __name__ == '__main__':
    datalist = [
        [0, 10, 1],
        [0, 11, 5],
        [1, 18, 2],
        [1, 12, 8],
        [1, 16, 6],
        [2, 8, 8],
        [2, 22, 3],
        [3, 24, 6],
        [3, 21, 8],
        [7, 16, 3],
        [7, 19, 6],
        [5, 17, 6],
        [4, 26, 5],
        [4, 7, 7],
        [4, 20, 3],
    ]

    aM = adjacencyMatrix(9, 9)
    for i in datalist:
        aM.createGraph(i[0], i[1], i[2])
    //MiniStpanTree = aM.primMinTree()
    aM.kruskalMinTree()

参考文献

• 《大话数据结构》