基于矩阵实现的最小生成树算法

Dear 丶 2022-08-18 02:17 80阅读 0赞

# 1.最小生成树 #

在 [Wikipedia][]中最小生成树（Minimum Spanning Tree）的定义如下：

> *A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the verticestogether with the minimal total weighting for its edges.*

但是，在本文中，我们主要介绍Prim算法，Prim算法同样可以在 [Wikipedia][Wikipedia 1]中找到：

> *In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.*

# 2.传统算法 #

## 2.1算法描述 ##

Prim的算法思想很简单：

1.  从图中任选一个结点，放入最小生成树集合中，
2.  重复操作：找最小生成树集合中所有结点的最近邻接点，然后再放入到最小生成树集合中，
3.  当访问完所有结点，即找到最小生成树。

下面对算法的图例描述：

![Center][]

## 2.2算法实现 ##

Python实现如下：

import numpy as np
    
    def prim(adjacencyMat, dimension, startVertex = 0):
        visited = np.zeros(dimension)
        distance = np.zeros(dimension)
        for i in range(dimension):
            distance[i] = np.inf
        tree = []
        tree.append(startVertex)
        visited[startVertex] = 1
        
        currentVertex = startVertex
        while not(len(tree) == dimension):
            for i in range(dimension):
                if not(adjacencyMat[currentVertex, i] == 0):
                    if (visited[i] == 0) and (distance[i] > adjacencyMat[currentVertex, i]):
                        distance[i] = adjacencyMat[currentVertex, i]
    #                     tree.append(i)
                        
            minDist = np.inf
            for i in range(dimension):
                if(visited[i] == 0) and (distance[i] < minDist):
                    minDist = distance[i]
                    currentVertex = i
            tree.append(currentVertex)
            visited[currentVertex] = 1
        print(tree)
        
    if __name__ == "__main__":
        adjacencyMat = np.array([[0,2,3,0,1],
                                 [0,0,0,0,7],
                                 [0,0,0,3,0],
                                 [0,0,0,0,0],
                                 [0,0,0,4,0]])   
        dimension = 5
        prim(adjacencyMat, dimension)

# 3.基于矩阵的实现 #

## 3.1算法描述 ##

既然要采用矩阵的方式，那么自然要用到邻接矩阵，邻接矩阵的定义如下：

![Center 1][]

同时，我们用一个向量s表示访问过的点集S，向量s定义：

![Center 2][]

另外，我们还需要一个向量d存储向量s中每个点对应的距离值，向量d定义：

![Center 3][]

假设有一个图，有5个点如：

![Center 4][]

那么其邻接矩阵是：

![Center 5][]

假设把点1作为起始点，那么起始向量是：

![Center 6][]

向量d初始是：

![Center 7][]

算法思想是，当向量s不全为无穷大（即结点没有访问完）时，重复以下三步：

1.  计算argmin(s+d)。即取出s+d的最小值对应的点u的标记或索引。
2.  把点u在向量s中对应位置的值改为无穷大。
3.  计算![Center 8][]表示点u到其他结点的距离，此时计算点u到点v的最小距离，如果点v在集合S中，那么点u到点v的距离是0；如果点v不在集合S中，那么求点u到点v的最小距离。如![Center 9][]，![Center 10][]，那么![Center 11][]，即对应索引位置去最小值。

## 3.2算法实现 ##

Python实现如下：

from numpy.random import rand
    import numpy as np
    
    def init(dimension, startVertex = 0):
        mat = rand(dimension, dimension)
        mat[(rand(dimension) * dimension).astype(int), (rand(dimension) * dimension).astype(int)] = np.inf
        vertexVec = np.zeros(dimension)
        for i in range(dimension):
            mat[i, i] = 0
        vertexVec[startVertex] = np.inf
        distanceVec = mat[0, :]
        return mat, vertexVec, distanceVec
    
    def minSpanningTree(adjacencyMat, vertexVec, distanceVec, startVertex, dimension):
        treeVec = []
        treeVec.append(startVertex)
        distanceVec = list(distanceVec)
        while(min(vertexVec) == 0):
            vertexId = distanceVec.index(min(distanceVec + vertexVec))
            vertexVec[vertexId] = np.inf
            treeVec.append(vertexId)
            for j in range(dimension):
                if adjacencyMat[vertexId, :][j] < distanceVec[j]:
                    distanceVec[j] = adjacencyMat[vertexId, :][j]
        print(treeVec)
    
    if __name__ == "__main__":
        dimension = 5
        startVertex = 0
        adjacencyMat, vertexVec, distanceVec = init(dimension, startVertex)
        adjacencyMat1 = np.array([[0,           2,     3, np.inf,      1],
                                 [np.inf,      0, np.inf, np.inf,      7],
                                 [np.inf, np.inf,      0,      3, np.inf],
                                 [np.inf, np.inf, np.inf,      0, np.inf],
                                 [np.inf, np.inf, np.inf,      4,      0]])
        distanceVec1 = adjacencyMat1[0, :]
        treeVec = []
        treeVec.append(startVertex)
        minSpanningTree(adjacencyMat1, vertexVec, distanceVec1, startVertex, dimension)

[Wikipedia]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
[Wikipedia 1]: https://en.wikipedia.org/wiki/Prim%27s_algorithm
[Center]: /images/20220731/1a68e98ff2034c18826d43d7fd764a53.png
[Center 1]: /images/20220731/cd46098f143141debe6aa49fe0268d1f.png
[Center 2]: /images/20220731/2b73e5f6cfa545caa2fbee9488271925.png
[Center 3]: /images/20220731/f230a512631d4c669ae90aaeebcc1bcb.png
[Center 4]: /images/20220731/56b4f758fc2a49ef9c42460429ee243b.png
[Center 5]: /images/20220731/93f912127fe64eeabea8fafb0af2ef6e.png
[Center 6]: /images/20220731/01d89486ea3049e689a9bbc41d5fa0c2.png
[Center 7]: /images/20220731/07c1fc6d373140a0b9228f98bf7ae063.png
[Center 8]: https://img-blog.csdn.net/20151205142256524?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 9]: https://img-blog.csdn.net/20151205142347989?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 10]: https://img-blog.csdn.net/20151205142420956?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 11]: /images/20220731/557074bca6b8426dad29a539f7d87263.png