python20行代码实现prim算法

import numpy
num = int(input("输入图中节点的个数："))
graph = numpy.zeros([num,num])
for i in range(0,num):
    for j in range(0,num):
        tap = input("请输入点{}到点{}的距离(-1为无穷远)".format(i,j))
        graph[i,j] = tap
while 1:
    select = int(input("选择你prim算法的起始节点:"))
    result = numpy.ones([num]) #定义已经选择的节点集合
    result[select] = 0 #加入到判定数组中
    while result.any() != 0:
        node = [0,0,1000]
        for i in range(0,num):
            if result[i] == 0:
                for j in range(0,num):
                    if node[2] > graph[i,j] and graph[i,j] != -1 and result[j] != 0:
                        node = [i,j,graph[i,j]] #更新比较量的值
        result[node[1]] = 0 #添加节点进入
        print("{}节点已经加入，从节点{}到节点{}且长度为{}".format(node[1],node[0],node[1],node[2]))

首先输入图中共有多少个点用num进行存储，然后使用python中的numpy数据分析库创建一个num*num大小的领接矩阵，然后进行num*num次循环，让用户初始化整个图，-1代表无穷远也代表自身到自身的距离。

虽然精简但好用！首先我们需要让用户输入起始的节点，然后创建一个num长全是1的数组，此数组用于后续的集合判断，也就是是否所有点都加入到了集合中。

首选肯定是将已选的点加入集合当中，然后开始while循环，.any()函数是指数组中所有元素只要有一个不为0则循环。第一个for循环是为了找到已经在集合中的某一个点，如果找到则进行对其相邻的所有边的遍历，如果边长小于我们设定的初始值无限大也就是1000，那么就将此长度存入到node节点中，并且存入从i到j点这个路径。当所有的已选节点都循环完一遍之后，我们会找到一个最小的边，将此边指向的节点存入到result数组中，然后打印输出最终结果，然后再讲node节点初始化即可。