关于有限连通图的prim算法的细节，可以参考https://my.oschina.net/u/4160637/blog/4359680

这里大致说明一下原理：

首先可以确定，假设某个联通图中，最短边必然在最小生成树里；由反证法可以轻易证明。同样的，我们还可以确定，某个图节点的最短边必然在最小生成树里；同样由反证法可以轻易证明。这就是Kruskal算法和Prim算法的依据。

Kruskal算法：首先图中所有图节点都创建为单元素的集合；然后将图的所有边按长短排序，依次从小到大取出每一条边。如果某条边它的两个节点分属不同集合，则记录该边，并合并两个集合；否则丢弃该边。如此往复，知道直到所有边均被处理完毕。Kruskal算法逻辑简洁明了，难点在于节点集合的创建、合并、查询。边排序有各种成熟算法，但集合的创建、合并、查询如果处理不好，会严重影响效率。关于这里，我的建议是，用固定长度数组和伪链表、查询更新来实现。

Prim算法：任意选取一图节点创建一个单元素的集合，同时创建一个该节点所有边构成的边集合。重复操作：从边集合中取出最短边，如果该边的另一图节点（设为P）不在节点集合内，则记录该边，将P加入节点集合，并将P的所有边加入边集合；否则丢弃该边。Prim算法只维护两个集合，但边集合需要频繁更新，且有一定排序需求。我的建议是，将边集合作为最小堆维护。同时，加入新边时尽可能缩减集合规模，比如，如果目的节点已在节点集合内就直接丢弃该边，如果已包含指向同一目的节点的边的话，则只保留较小的边

变种Prim算法：也可以说是Prim算法和Kruskal算法的结合。首先，对所有节点，都创建为包含一个节点集合和边集合的对象，遍历所有对象并记录其最短边，同时合并最短边两侧的对象（点集合、边集合分别合并）。重复这一过程，直到只剩一个对象为止。该法缺点不用我说也很明显了，一般只在稠密图中（比如任意两节点都有边连接，节点数量极大）才有使用价值。

以下是三种算法的实现示例。

package main

import (
	"fmt"
)

// 两节点间的距离
type Distance struct {
	F, T int     // 起点 终点
	D    float64 // 距离
}

// 距离统计树堆的节点结构
type Node struct {
	Distance
	B, L, R *Node // 父亲，左子，右子
}

// 树堆的封装，以目的节点排序，而以距离构建最小堆
type Heap struct{ *Node } // 树堆根节点

const N = 41

var (
	// 距离矩阵
	MTX = [41][41]float64{
		{1.00000000000000000, 0.76056338028169010, 0.72222222222222220, 0.85333333333333340, 0.82191780821917800, 0.68493150684931500, 0.79452054794520540, 0.42857142857142855, 0.71428571428571430, 0.49315068493150680, 0.63888888888888880, 0.54054054054054060, 0.48717948717948717, 0.46153846153846156, 0.67605633802816900, 0.61971830985915490, 0.60273972602739720, 0.35616438356164380, 0.76315789473684210, 0.76315789473684210, 0.44736842105263160, 0.64102564102564110, 0.75324675324675330, 0.71604938271604930, 0.76315789473684210, 0.60240963855421690, 0.73417721518987340, 0.62650602409638560, 0.45238095238095240, 0.61904761904761910, 0.61904761904761910, 0.44705882352941180, 0.48780487804878050, 0.77922077922077930, 0.49382716049382713, 0.30379746835443040, 0.25000000000000000, 0.25000000000000000, 0.28205128205128205, 0.38554216867469880, 0.69879518072289160},
		{0.76056338028169010, 1.00000000000000000, 0.58666666666666670, 0.69230769230769230, 0.63157894736842100, 0.55263157894736850, 0.57894736842105270, 0.41095890410958900, 0.63013698630136980, 0.42105263157894735, 0.53333333333333330, 0.46753246753246750, 0.41975308641975306, 0.37037037037037035, 0.62162162162162160, 0.59459459459459460, 0.57894736842105270, 0.34210526315789475, 0.55696202531645570, 0.55696202531645570, 0.40506329113924050, 0.46913580246913580, 0.55000000000000000, 0.52380952380952380, 0.55696202531645570, 0.44186046511627910, 0.53658536585365860, 0.46511627906976744, 0.62068965517241380, 0.45977011494252873, 0.45977011494252873, 0.61363636363636360, 0.37647058823529410, 0.57500000000000000, 0.71428571428571430, 0.29268292682926830, 0.24096385542168675, 0.24096385542168675, 0.27160493827160490, 0.34883720930232560, 0.51162790697674420},
		{0.72222222222222220, 0.58666666666666670, 1.00000000000000000, 0.68354430379746830, 0.64935064935064930, 0.64935064935064930, 0.57142857142857140, 0.35135135135135137, 0.59459459459459460, 0.44155844155844154, 0.57894736842105270, 0.46153846153846156, 0.43902439024390244, 0.39024390243902440, 0.56000000000000000, 0.50666666666666670, 0.51948051948051940, 0.31168831168831170, 0.55000000000000000, 0.55000000000000000, 0.35000000000000000, 0.53658536585365860, 0.56790123456790120, 0.51764705882352950, 0.57500000000000000, 0.50574712643678170, 0.55421686746987950, 0.52873563218390810, 0.40909090909090910, 0.54545454545454540, 0.54545454545454540, 0.42696629213483145, 0.44186046511627910, 0.56790123456790120, 0.40000000000000000, 0.24096385542168675, 0.23809523809523808, 0.23809523809523808, 0.24390243902439024, 0.29885057471264370, 0.48275862068965520},
		{0.85333333333333340, 0.69230769230769230, 0.68354430379746830, 1.00000000000000000, 0.72500000000000000, 0.62500000000000000, 0.70000000000000000, 0.41558441558441560, 0.64935064935064930, 0.47500000000000000, 0.60759493670886080, 0.56790123456790120, 0.54117647058823530, 0.49411764705882355, 0.61538461538461540, 0.58974358974358980, 0.57500000000000000, 0.35000000000000000, 0.67469879518072280, 0.67469879518072280, 0.40963855421686746, 0.58823529411764710, 0.66666666666666660, 0.63636363636363640, 0.67469879518072280, 0.60000000000000000, 0.69767441860465120, 0.62222222222222220, 0.48351648351648350, 0.61538461538461540, 0.61538461538461540, 0.47826086956521740, 0.47191011235955055, 0.73809523809523810, 0.52272727272727270, 0.32558139534883723, 0.27586206896551724, 0.27586206896551724, 0.30588235294117650, 0.37777777777777777, 0.62222222222222220},
		{0.82191780821917800, 0.63157894736842100, 0.64935064935064930, 0.72500000000000000, 1.00000000000000000, 0.64102564102564110, 0.66666666666666660, 0.34666666666666670, 0.64000000000000000, 0.46153846153846156, 0.57142857142857140, 0.50632911392405070, 0.45783132530120480, 0.43373493975903615, 0.55263157894736850, 0.50000000000000000, 0.53846153846153840, 0.33333333333333330, 0.64197530864197530, 0.66666666666666660, 0.39506172839506170, 0.77108433734939760, 0.63414634146341460, 0.60465116279069760, 0.64197530864197530, 0.56818181818181820, 0.61904761904761910, 0.72727272727272730, 0.51685393258426970, 0.56179775280898880, 0.56179775280898880, 0.40000000000000000, 0.43678160919540230, 0.65853658536585370, 0.41860465116279070, 0.23809523809523808, 0.21176470588235294, 0.21176470588235294, 0.24096385542168675, 0.31818181818181820, 0.59090909090909090},
		{0.68493150684931500, 0.55263157894736850, 0.64935064935064930, 0.62500000000000000, 0.64102564102564110, 1.00000000000000000, 0.53846153846153840, 0.32000000000000000, 0.61333333333333330, 0.46153846153846156, 0.62337662337662340, 0.50632911392405070, 0.45783132530120480, 0.40963855421686746, 0.52631578947368420, 0.44736842105263160, 0.48717948717948717, 0.30769230769230770, 0.51851851851851850, 0.51851851851851850, 0.34567901234567900, 0.50602409638554210, 0.51219512195121950, 0.48837209302325580, 0.51851851851851850, 0.47727272727272730, 0.50000000000000000, 0.47727272727272730, 0.38202247191011235, 0.47191011235955055, 0.47191011235955055, 0.35555555555555557, 0.41379310344827586, 0.53658536585365860, 0.39534883720930230, 0.23809523809523808, 0.23529411764705882, 0.23529411764705882, 0.24096385542168675, 0.31818181818181820, 0.50000000000000000},
		{0.79452054794520540, 0.57894736842105270, 0.57142857142857140, 0.70000000000000000, 0.66666666666666660, 0.53846153846153840, 1.00000000000000000, 0.66666666666666660, 0.53333333333333330, 0.71794871794871800, 0.46753246753246750, 0.43037974683544306, 0.43373493975903615, 0.43373493975903615, 0.55263157894736850, 0.57894736842105270, 0.46153846153846156, 0.58974358974358980, 0.83950617283950610, 0.83950617283950610, 0.56790123456790120, 0.69879518072289160, 0.73170731707317070, 0.69767441860465120, 0.74074074074074070, 0.68181818181818180, 0.71428571428571430, 0.61363636363636360, 0.44943820224719100, 0.62921348314606740, 0.62921348314606740, 0.46666666666666670, 0.48275862068965520, 0.73170731707317070, 0.58139534883720930, 0.42857142857142855, 0.35294117647058826, 0.35294117647058826, 0.40963855421686746, 0.52272727272727270, 0.77272727272727270},
		{0.42857142857142855, 0.41095890410958900, 0.35135135135135137, 0.41558441558441560, 0.34666666666666670, 0.32000000000000000, 0.66666666666666660, 1.00000000000000000, 0.36111111111111110, 0.61333333333333330, 0.32432432432432434, 0.31578947368421050, 0.32500000000000000, 0.30000000000000000, 0.46575342465753420, 0.65753424657534240, 0.37333333333333335, 0.56000000000000000, 0.51282051282051280, 0.51282051282051280, 0.48717948717948717, 0.42500000000000000, 0.40506329113924050, 0.38554216867469880, 0.41025641025641024, 0.42352941176470590, 0.39506172839506170, 0.35294117647058826, 0.34883720930232560, 0.37209302325581395, 0.37209302325581395, 0.36781609195402300, 0.33333333333333330, 0.40506329113924050, 0.48192771084337350, 0.54320987654320980, 0.41463414634146340, 0.41463414634146340, 0.42500000000000000, 0.44705882352941180, 0.47058823529411764},
		{0.71428571428571430, 0.63013698630136980, 0.59459459459459460, 0.64935064935064930, 0.64000000000000000, 0.61333333333333330, 0.53333333333333330, 0.36111111111111110, 1.00000000000000000, 0.77333333333333330, 0.64864864864864870, 0.81578947368421050, 0.65000000000000000, 0.60000000000000000, 0.57534246575342460, 0.54794520547945200, 0.61333333333333330, 0.37333333333333335, 0.51282051282051280, 0.51282051282051280, 0.35897435897435900, 0.47500000000000000, 0.50632911392405070, 0.48192771084337350, 0.51282051282051280, 0.44705882352941180, 0.49382716049382713, 0.44705882352941180, 0.37209302325581395, 0.44186046511627910, 0.44186046511627910, 0.36781609195402300, 0.40476190476190477, 0.53164556962025310, 0.38554216867469880, 0.24691358024691357, 0.21951219512195122, 0.21951219512195122, 0.25000000000000000, 0.30588235294117650, 0.47058823529411764},
		{0.49315068493150680, 0.42105263157894735, 0.44155844155844154, 0.47500000000000000, 0.46153846153846156, 0.46153846153846156, 0.71794871794871800, 0.61333333333333330, 0.77333333333333330, 1.00000000000000000, 0.46753246753246750, 0.70886075949367090, 0.60240963855421690, 0.57831325301204820, 0.42105263157894735, 0.47368421052631576, 0.43589743589743590, 0.61538461538461540, 0.56790123456790120, 0.56790123456790120, 0.44444444444444440, 0.53012048192771090, 0.46341463414634150, 0.44186046511627910, 0.46913580246913580, 0.52272727272727270, 0.45238095238095240, 0.43181818181818180, 0.38202247191011235, 0.44943820224719100, 0.44943820224719100, 0.40000000000000000, 0.39080459770114945, 0.46341463414634150, 0.48837209302325580, 0.38095238095238093, 0.32941176470588235, 0.32941176470588235, 0.38554216867469880, 0.40909090909090910, 0.52272727272727270},
		{0.63888888888888880, 0.53333333333333330, 0.57894736842105270, 0.60759493670886080, 0.57142857142857140, 0.62337662337662340, 0.46753246753246750, 0.32432432432432434, 0.64864864864864870, 0.46753246753246750, 1.00000000000000000, 0.51282051282051280, 0.46341463414634150, 0.41463414634146340, 0.50666666666666670, 0.48000000000000000, 0.51948051948051940, 0.31168831168831170, 0.45000000000000000, 0.45000000000000000, 0.30000000000000000, 0.43902439024390244, 0.44444444444444440, 0.42352941176470590, 0.45000000000000000, 0.41379310344827586, 0.43373493975903615, 0.41379310344827586, 0.31818181818181820, 0.40909090909090910, 0.40909090909090910, 0.31460674157303370, 0.41860465116279070, 0.46913580246913580, 0.35294117647058826, 0.24096385542168675, 0.23809523809523808, 0.23809523809523808, 0.24390243902439024, 0.27586206896551724, 0.43678160919540230},
		{0.54054054054054060, 0.46753246753246750, 0.46153846153846156, 0.56790123456790120, 0.50632911392405070, 0.50632911392405070, 0.43037974683544306, 0.31578947368421050, 0.81578947368421050, 0.70886075949367090, 0.51282051282051280, 1.00000000000000000, 0.78571428571428570, 0.71428571428571430, 0.41558441558441560, 0.38961038961038963, 0.45569620253164556, 0.32911392405063290, 0.43902439024390244, 0.41463414634146340, 0.26829268292682930, 0.40476190476190477, 0.40963855421686746, 0.39080459770114945, 0.41463414634146340, 0.40449438202247190, 0.42352941176470590, 0.40449438202247190, 0.35555555555555557, 0.40000000000000000, 0.40000000000000000, 0.35164835164835170, 0.34090909090909090, 0.45783132530120480, 0.36781609195402300, 0.23529411764705882, 0.20930232558139536, 0.20930232558139536, 0.23809523809523808, 0.24719101123595505, 0.40449438202247190},
		{0.48717948717948717, 0.41975308641975306, 0.43902439024390244, 0.54117647058823530, 0.45783132530120480, 0.45783132530120480, 0.43373493975903615, 0.32500000000000000, 0.65000000000000000, 0.60240963855421690, 0.46341463414634150, 0.78571428571428570, 1.00000000000000000, 0.70454545454545460, 0.41975308641975306, 0.39506172839506170, 0.43373493975903615, 0.33734939759036140, 0.39534883720930230, 0.39534883720930230, 0.27906976744186046, 0.38636363636363635, 0.39080459770114945, 0.37362637362637363, 0.39534883720930230, 0.45161290322580644, 0.40449438202247190, 0.38709677419354840, 0.34042553191489360, 0.44680851063829785, 0.44680851063829785, 0.40000000000000000, 0.32608695652173914, 0.43678160919540230, 0.35164835164835170, 0.24719101123595505, 0.26666666666666666, 0.26666666666666666, 0.27272727272727270, 0.25806451612903225, 0.36559139784946240},
		{0.46153846153846156, 0.37037037037037035, 0.39024390243902440, 0.49411764705882355, 0.43373493975903615, 0.40963855421686746, 0.43373493975903615, 0.30000000000000000, 0.60000000000000000, 0.57831325301204820, 0.41463414634146340, 0.71428571428571430, 0.70454545454545460, 1.00000000000000000, 0.37037037037037035, 0.32098765432098764, 0.43373493975903615, 0.36144578313253010, 0.41860465116279070, 0.41860465116279070, 0.27906976744186046, 0.40909090909090910, 0.41379310344827586, 0.39560439560439560, 0.41860465116279070, 0.38709677419354840, 0.42696629213483145, 0.40860215053763443, 0.36170212765957450, 0.38297872340425530, 0.38297872340425530, 0.33684210526315790, 0.32608695652173914, 0.45977011494252873, 0.35164835164835170, 0.22471910112359550, 0.20000000000000000, 0.20000000000000000, 0.22727272727272727, 0.25806451612903225, 0.38709677419354840},
		{0.67605633802816900, 0.62162162162162160, 0.56000000000000000, 0.61538461538461540, 0.55263157894736850, 0.52631578947368420, 0.55263157894736850, 0.46575342465753420, 0.57534246575342460, 0.42105263157894735, 0.50666666666666670, 0.41558441558441560, 0.41975308641975306, 0.37037037037037035, 1.00000000000000000, 0.67567567567567570, 0.57894736842105270, 0.36842105263157890, 0.50632911392405070, 0.50632911392405070, 0.75949367088607600, 0.41975308641975306, 0.50000000000000000, 0.47619047619047616, 0.50632911392405070, 0.41860465116279070, 0.48780487804878050, 0.41860465116279070, 0.39080459770114945, 0.43678160919540230, 0.43678160919540230, 0.40909090909090910, 0.37647058823529410, 0.52500000000000000, 0.40476190476190477, 0.36585365853658536, 0.33734939759036140, 0.33734939759036140, 0.37037037037037035, 0.67441860465116280, 0.44186046511627910},
		{0.61971830985915490, 0.59459459459459460, 0.50666666666666670, 0.58974358974358980, 0.50000000000000000, 0.44736842105263160, 0.57894736842105270, 0.65753424657534240, 0.54794520547945200, 0.47368421052631576, 0.48000000000000000, 0.38961038961038963, 0.39506172839506170, 0.32098765432098764, 0.67567567567567570, 1.00000000000000000, 0.55263157894736850, 0.42105263157894735, 0.53164556962025310, 0.53164556962025310, 0.53164556962025310, 0.41975308641975306, 0.45000000000000000, 0.45238095238095240, 0.45569620253164556, 0.41860465116279070, 0.43902439024390244, 0.37209302325581395, 0.34482758620689660, 0.39080459770114945, 0.39080459770114945, 0.36363636363636365, 0.35294117647058826, 0.47500000000000000, 0.45238095238095240, 0.65853658536585370, 0.50602409638554210, 0.50602409638554210, 0.49382716049382713, 0.46511627906976744, 0.46511627906976744},
		{0.60273972602739720, 0.57894736842105270, 0.51948051948051940, 0.57500000000000000, 0.53846153846153840, 0.48717948717948717, 0.46153846153846156, 0.37333333333333335, 0.61333333333333330, 0.43589743589743590, 0.51948051948051940, 0.45569620253164556, 0.43373493975903615, 0.43373493975903615, 0.57894736842105270, 0.55263157894736850, 1.00000000000000000, 0.76923076923076930, 0.44444444444444440, 0.44444444444444440, 0.37037037037037035, 0.40963855421686746, 0.46341463414634150, 0.41860465116279070, 0.44444444444444440, 0.38636363636363635, 0.42857142857142855, 0.38636363636363635, 0.35955056179775280, 0.38202247191011235, 0.38202247191011235, 0.35555555555555557, 0.34482758620689660, 0.48780487804878050, 0.37209302325581395, 0.26190476190476190, 0.23529411764705882, 0.23529411764705882, 0.26506024096385544, 0.31818181818181820, 0.38636363636363635},
		{0.35616438356164380, 0.34210526315789475, 0.31168831168831170, 0.35000000000000000, 0.33333333333333330, 0.30769230769230770, 0.58974358974358980, 0.56000000000000000, 0.37333333333333335, 0.61538461538461540, 0.31168831168831170, 0.32911392405063290, 0.33734939759036140, 0.36144578313253010, 0.36842105263157890, 0.42105263157894735, 0.76923076923076930, 1.00000000000000000, 0.44444444444444440, 0.44444444444444440, 0.41975308641975306, 0.40963855421686746, 0.36585365853658536, 0.32558139534883723, 0.34567901234567900, 0.40909090909090910, 0.33333333333333330, 0.31818181818181820, 0.31460674157303370, 0.33707865168539325, 0.33707865168539325, 0.33333333333333330, 0.27586206896551724, 0.36585365853658536, 0.41860465116279070, 0.35714285714285715, 0.30588235294117650, 0.30588235294117650, 0.36144578313253010, 0.40909090909090910, 0.40909090909090910},
		{0.76315789473684210, 0.55696202531645570, 0.55000000000000000, 0.67469879518072280, 0.64197530864197530, 0.51851851851851850, 0.83950617283950610, 0.51282051282051280, 0.51282051282051280, 0.56790123456790120, 0.45000000000000000, 0.43902439024390244, 0.39534883720930230, 0.41860465116279070, 0.50632911392405070, 0.53164556962025310, 0.44444444444444440, 0.44444444444444440, 1.00000000000000000, 0.90476190476190480, 0.61904761904761910, 0.74418604651162790, 0.70588235294117650, 0.69662921348314610, 0.73809523809523810, 0.70329670329670340, 0.71264367816091960, 0.61538461538461540, 0.45652173913043476, 0.60869565217391310, 0.60869565217391310, 0.45161290322580644, 0.48888888888888890, 0.70588235294117650, 0.56179775280898880, 0.43678160919540230, 0.36363636363636365, 0.36363636363636365, 0.41860465116279070, 0.46153846153846156, 0.72527472527472530},
		{0.76315789473684210, 0.55696202531645570, 0.55000000000000000, 0.67469879518072280, 0.66666666666666660, 0.51851851851851850, 0.83950617283950610, 0.51282051282051280, 0.51282051282051280, 0.56790123456790120, 0.45000000000000000, 0.41463414634146340, 0.39534883720930230, 0.41860465116279070, 0.50632911392405070, 0.53164556962025310, 0.44444444444444440, 0.44444444444444440, 0.90476190476190480, 1.00000000000000000, 0.71428571428571430, 0.83720930232558140, 0.70588235294117650, 0.71910112359550560, 0.76190476190476190, 0.70329670329670340, 0.71264367816091960, 0.63736263736263730, 0.47826086956521740, 0.60869565217391310, 0.60869565217391310, 0.45161290322580644, 0.51111111111111110, 0.70588235294117650, 0.56179775280898880, 0.41379310344827586, 0.34090909090909090, 0.34090909090909090, 0.39534883720930230, 0.46153846153846156, 0.72527472527472530},
		{0.44736842105263160, 0.40506329113924050, 0.35000000000000000, 0.40963855421686746, 0.39506172839506170, 0.34567901234567900, 0.56790123456790120, 0.48717948717948717, 0.35897435897435900, 0.44444444444444440, 0.30000000000000000, 0.26829268292682930, 0.27906976744186046, 0.27906976744186046, 0.75949367088607600, 0.53164556962025310, 0.37037037037037035, 0.41975308641975306, 0.61904761904761910, 0.71428571428571430, 1.00000000000000000, 0.58139534883720930, 0.42352941176470590, 0.44943820224719100, 0.47619047619047616, 0.48351648351648350, 0.43678160919540230, 0.39560439560439560, 0.36956521739130430, 0.39130434782608700, 0.39130434782608700, 0.36559139784946240, 0.35555555555555557, 0.42352941176470590, 0.42696629213483145, 0.45977011494252873, 0.40909090909090910, 0.40909090909090910, 0.46511627906976744, 0.72527472527472530, 0.46153846153846156},
		{0.64102564102564110, 0.46913580246913580, 0.53658536585365860, 0.58823529411764710, 0.77108433734939760, 0.50602409638554210, 0.69879518072289160, 0.42500000000000000, 0.47500000000000000, 0.53012048192771090, 0.43902439024390244, 0.40476190476190477, 0.38636363636363635, 0.40909090909090910, 0.41975308641975306, 0.41975308641975306, 0.40963855421686746, 0.40963855421686746, 0.74418604651162790, 0.83720930232558140, 0.58139534883720930, 1.00000000000000000, 0.59770114942528740, 0.61538461538461540, 0.65116279069767450, 0.68817204301075270, 0.60674157303370790, 0.73118279569892470, 0.53191489361702130, 0.57446808510638300, 0.57446808510638300, 0.42105263157894735, 0.47826086956521740, 0.59770114942528740, 0.48351648351648350, 0.33707865168539325, 0.28888888888888886, 0.28888888888888886, 0.34090909090909090, 0.36559139784946240, 0.60215053763440860},
		{0.75324675324675330, 0.55000000000000000, 0.56790123456790120, 0.66666666666666660, 0.63414634146341460, 0.51219512195121950, 0.73170731707317070, 0.40506329113924050, 0.50632911392405070, 0.46341463414634150, 0.44444444444444440, 0.40963855421686746, 0.39080459770114945, 0.41379310344827586, 0.50000000000000000, 0.45000000000000000, 0.46341463414634150, 0.36585365853658536, 0.70588235294117650, 0.70588235294117650, 0.42352941176470590, 0.59770114942528740, 1.00000000000000000, 0.71111111111111110, 0.80000000000000000, 0.56521739130434780, 0.77272727272727270, 0.65217391304347830, 0.49462365591397850, 0.64516129032258060, 0.64516129032258060, 0.48936170212765956, 0.50549450549450550, 0.72093023255813950, 0.46666666666666670, 0.29545454545454547, 0.24719101123595505, 0.24719101123595505, 0.27586206896551724, 0.36956521739130430, 0.63043478260869570},
		{0.71604938271604930, 0.52380952380952380, 0.51764705882352950, 0.63636363636363640, 0.60465116279069760, 0.48837209302325580, 0.69767441860465120, 0.38554216867469880, 0.48192771084337350, 0.44186046511627910, 0.42352941176470590, 0.39080459770114945, 0.37362637362637363, 0.39560439560439560, 0.47619047619047616, 0.45238095238095240, 0.41860465116279070, 0.32558139534883723, 0.69662921348314610, 0.71910112359550560, 0.44943820224719100, 0.61538461538461540, 0.71111111111111110, 1.00000000000000000, 0.78651685393258430, 0.56250000000000000, 0.71739130434782600, 0.60416666666666660, 0.45360824742268040, 0.59793814432989690, 0.59793814432989690, 0.44897959183673470, 0.54736842105263160, 0.66666666666666660, 0.44680851063829785, 0.32608695652173914, 0.27956989247311825, 0.27956989247311825, 0.30769230769230770, 0.35416666666666670, 0.60416666666666660},
		{0.76315789473684210, 0.55696202531645570, 0.57500000000000000, 0.67469879518072280, 0.64197530864197530, 0.51851851851851850, 0.74074074074074070, 0.41025641025641024, 0.51282051282051280, 0.46913580246913580, 0.45000000000000000, 0.41463414634146340, 0.39534883720930230, 0.41860465116279070, 0.50632911392405070, 0.45569620253164556, 0.44444444444444440, 0.34567901234567900, 0.73809523809523810, 0.76190476190476190, 0.47619047619047616, 0.65116279069767450, 0.80000000000000000, 0.78651685393258430, 1.00000000000000000, 0.59340659340659340, 0.87356321839080460, 0.72527472527472530, 0.56521739130434780, 0.71739130434782600, 0.71739130434782600, 0.55913978494623650, 0.57777777777777770, 0.70588235294117650, 0.47191011235955055, 0.32183908045977010, 0.27272727272727270, 0.27272727272727270, 0.30232558139534880, 0.37362637362637363, 0.63736263736263730},
		{0.60240963855421690, 0.44186046511627910, 0.50574712643678170, 0.60000000000000000, 0.56818181818181820, 0.47727272727272730, 0.68181818181818180, 0.42352941176470590, 0.44705882352941180, 0.52272727272727270, 0.41379310344827586, 0.40449438202247190, 0.45161290322580644, 0.38709677419354840, 0.41860465116279070, 0.41860465116279070, 0.38636363636363635, 0.40909090909090910, 0.70329670329670340, 0.70329670329670340, 0.48351648351648350, 0.68817204301075270, 0.56521739130434780, 0.56250000000000000, 0.59340659340659340, 1.00000000000000000, 0.63829787234042560, 0.61224489795918370, 0.46464646464646464, 0.76767676767676760, 0.76767676767676760, 0.58000000000000000, 0.43298969072164950, 0.60869565217391310, 0.50000000000000000, 0.36170212765957450, 0.33684210526315790, 0.33684210526315790, 0.38709677419354840, 0.38775510204081630, 0.59183673469387750},
		{0.73417721518987340, 0.53658536585365860, 0.55421686746987950, 0.69767441860465120, 0.61904761904761910, 0.50000000000000000, 0.71428571428571430, 0.39506172839506170, 0.49382716049382713, 0.45238095238095240, 0.43373493975903615, 0.42352941176470590, 0.40449438202247190, 0.42696629213483145, 0.48780487804878050, 0.43902439024390244, 0.42857142857142855, 0.33333333333333330, 0.71264367816091960, 0.71264367816091960, 0.43678160919540230, 0.60674157303370790, 0.77272727272727270, 0.71739130434782600, 0.87356321839080460, 0.63829787234042560, 1.00000000000000000, 0.85106382978723400, 0.69473684210526320, 0.84210526315789470, 0.84210526315789470, 0.68750000000000000, 0.51612903225806450, 0.72727272727272730, 0.50000000000000000, 0.33333333333333330, 0.28571428571428570, 0.28571428571428570, 0.31460674157303370, 0.38297872340425530, 0.63829787234042560},
		{0.62650602409638560, 0.46511627906976744, 0.52873563218390810, 0.62222222222222220, 0.72727272727272730, 0.47727272727272730, 0.61363636363636360, 0.35294117647058826, 0.44705882352941180, 0.43181818181818180, 0.41379310344827586, 0.40449438202247190, 0.38709677419354840, 0.40860215053763443, 0.41860465116279070, 0.37209302325581395, 0.38636363636363635, 0.31818181818181820, 0.61538461538461540, 0.63736263736263730, 0.39560439560439560, 0.73118279569892470, 0.65217391304347830, 0.60416666666666660, 0.72527472527472530, 0.61224489795918370, 0.85106382978723400, 1.00000000000000000, 0.80808080808080810, 0.80808080808080810, 0.80808080808080810, 0.66000000000000000, 0.47422680412371130, 0.63043478260869570, 0.45833333333333330, 0.29787234042553190, 0.27368421052631580, 0.27368421052631580, 0.30107526881720430, 0.32653061224489793, 0.55102040816326530},
		{0.45238095238095240, 0.62068965517241380, 0.40909090909090910, 0.48351648351648350, 0.51685393258426970, 0.38202247191011235, 0.44943820224719100, 0.34883720930232560, 0.37209302325581395, 0.38202247191011235, 0.31818181818181820, 0.35555555555555557, 0.34042553191489360, 0.36170212765957450, 0.39080459770114945, 0.34482758620689660, 0.35955056179775280, 0.31460674157303370, 0.45652173913043476, 0.47826086956521740, 0.36956521739130430, 0.53191489361702130, 0.49462365591397850, 0.45360824742268040, 0.56521739130434780, 0.46464646464646464, 0.69473684210526320, 0.80808080808080810, 1.00000000000000000, 0.66000000000000000, 0.66000000000000000, 0.81188118811881190, 0.36734693877551020, 0.47311827956989250, 0.61855670103092790, 0.29473684210526313, 0.27083333333333330, 0.27083333333333330, 0.29787234042553190, 0.30303030303030304, 0.40404040404040403},
		{0.61904761904761910, 0.45977011494252873, 0.54545454545454540, 0.61538461538461540, 0.56179775280898880, 0.47191011235955055, 0.62921348314606740, 0.37209302325581395, 0.44186046511627910, 0.44943820224719100, 0.40909090909090910, 0.40000000000000000, 0.44680851063829785, 0.38297872340425530, 0.43678160919540230, 0.39080459770114945, 0.38202247191011235, 0.33707865168539325, 0.60869565217391310, 0.60869565217391310, 0.39130434782608700, 0.57446808510638300, 0.64516129032258060, 0.59793814432989690, 0.71739130434782600, 0.76767676767676760, 0.84210526315789470, 0.80808080808080810, 0.66000000000000000, 1.00000000000000000, 1.00000000000000000, 0.81188118811881190, 0.46938775510204084, 0.62365591397849460, 0.45360824742268040, 0.31578947368421050, 0.31250000000000000, 0.31250000000000000, 0.34042553191489360, 0.34343434343434340, 0.54545454545454540},
		{0.61904761904761910, 0.45977011494252873, 0.54545454545454540, 0.61538461538461540, 0.56179775280898880, 0.47191011235955055, 0.62921348314606740, 0.37209302325581395, 0.44186046511627910, 0.44943820224719100, 0.40909090909090910, 0.40000000000000000, 0.44680851063829785, 0.38297872340425530, 0.43678160919540230, 0.39080459770114945, 0.38202247191011235, 0.33707865168539325, 0.60869565217391310, 0.60869565217391310, 0.39130434782608700, 0.57446808510638300, 0.64516129032258060, 0.59793814432989690, 0.71739130434782600, 0.76767676767676760, 0.84210526315789470, 0.80808080808080810, 0.66000000000000000, 1.00000000000000000, 1.00000000000000000, 0.81188118811881190, 0.46938775510204084, 0.62365591397849460, 0.45360824742268040, 0.31578947368421050, 0.31250000000000000, 0.31250000000000000, 0.34042553191489360, 0.34343434343434340, 0.54545454545454540},
		{0.44705882352941180, 0.61363636363636360, 0.42696629213483145, 0.47826086956521740, 0.40000000000000000, 0.35555555555555557, 0.46666666666666670, 0.36781609195402300, 0.36781609195402300, 0.40000000000000000, 0.31460674157303370, 0.35164835164835170, 0.40000000000000000, 0.33684210526315790, 0.40909090909090910, 0.36363636363636365, 0.35555555555555557, 0.33333333333333330, 0.45161290322580644, 0.45161290322580644, 0.36559139784946240, 0.42105263157894735, 0.48936170212765956, 0.44897959183673470, 0.55913978494623650, 0.58000000000000000, 0.68750000000000000, 0.66000000000000000, 0.81188118811881190, 0.81188118811881190, 0.81188118811881190, 1.00000000000000000, 0.36363636363636365, 0.46808510638297873, 0.61224489795918370, 0.31250000000000000, 0.30927835051546393, 0.30927835051546393, 0.33684210526315790, 0.32000000000000000, 0.40000000000000000},
		{0.48780487804878050, 0.37647058823529410, 0.44186046511627910, 0.47191011235955055, 0.43678160919540230, 0.41379310344827586, 0.48275862068965520, 0.33333333333333330, 0.40476190476190477, 0.39080459770114945, 0.41860465116279070, 0.34090909090909090, 0.32608695652173914, 0.32608695652173914, 0.37647058823529410, 0.35294117647058826, 0.34482758620689660, 0.27586206896551724, 0.48888888888888890, 0.51111111111111110, 0.35555555555555557, 0.47826086956521740, 0.50549450549450550, 0.54736842105263160, 0.57777777777777770, 0.43298969072164950, 0.51612903225806450, 0.47422680412371130, 0.36734693877551020, 0.46938775510204084, 0.46938775510204084, 0.36363636363636365, 1.00000000000000000, 0.46153846153846156, 0.33684210526315790, 0.25806451612903225, 0.25531914893617020, 0.25531914893617020, 0.26086956521739130, 0.26804123711340205, 0.41237113402061853},
		{0.77922077922077930, 0.57500000000000000, 0.56790123456790120, 0.73809523809523810, 0.65853658536585370, 0.53658536585365860, 0.73170731707317070, 0.40506329113924050, 0.53164556962025310, 0.46341463414634150, 0.46913580246913580, 0.45783132530120480, 0.43678160919540230, 0.45977011494252873, 0.52500000000000000, 0.47500000000000000, 0.48780487804878050, 0.36585365853658536, 0.70588235294117650, 0.70588235294117650, 0.42352941176470590, 0.59770114942528740, 0.72093023255813950, 0.66666666666666660, 0.70588235294117650, 0.60869565217391310, 0.72727272727272730, 0.63043478260869570, 0.47311827956989250, 0.62365591397849460, 0.62365591397849460, 0.46808510638297873, 0.46153846153846156, 1.00000000000000000, 0.57777777777777770, 0.36363636363636365, 0.31460674157303370, 0.31460674157303370, 0.34482758620689660, 0.43478260869565216, 0.69565217391304350},
		{0.49382716049382713, 0.71428571428571430, 0.40000000000000000, 0.52272727272727270, 0.41860465116279070, 0.39534883720930230, 0.58139534883720930, 0.48192771084337350, 0.38554216867469880, 0.48837209302325580, 0.35294117647058826, 0.36781609195402300, 0.35164835164835170, 0.35164835164835170, 0.40476190476190477, 0.45238095238095240, 0.37209302325581395, 0.41860465116279070, 0.56179775280898880, 0.56179775280898880, 0.42696629213483145, 0.48351648351648350, 0.46666666666666670, 0.44680851063829785, 0.47191011235955055, 0.50000000000000000, 0.50000000000000000, 0.45833333333333330, 0.61855670103092790, 0.45360824742268040, 0.45360824742268040, 0.61224489795918370, 0.33684210526315790, 0.57777777777777770, 1.00000000000000000, 0.54347826086956520, 0.47311827956989250, 0.47311827956989250, 0.52747252747252750, 0.54166666666666660, 0.66666666666666660},
		{0.30379746835443040, 0.29268292682926830, 0.24096385542168675, 0.32558139534883723, 0.23809523809523808, 0.23809523809523808, 0.42857142857142855, 0.54320987654320980, 0.24691358024691357, 0.38095238095238093, 0.24096385542168675, 0.23529411764705882, 0.24719101123595505, 0.22471910112359550, 0.36585365853658536, 0.65853658536585370, 0.26190476190476190, 0.35714285714285715, 0.43678160919540230, 0.41379310344827586, 0.45977011494252873, 0.33707865168539325, 0.29545454545454547, 0.32608695652173914, 0.32183908045977010, 0.36170212765957450, 0.33333333333333330, 0.29787234042553190, 0.29473684210526313, 0.31578947368421050, 0.31578947368421050, 0.31250000000000000, 0.25806451612903225, 0.36363636363636365, 0.54347826086956520, 1.00000000000000000, 0.85714285714285710, 0.85714285714285710, 0.85393258426966290, 0.59574468085106380, 0.55319148936170210},
		{0.25000000000000000, 0.24096385542168675, 0.23809523809523808, 0.27586206896551724, 0.21176470588235294, 0.23529411764705882, 0.35294117647058826, 0.41463414634146340, 0.21951219512195122, 0.32941176470588235, 0.23809523809523808, 0.20930232558139536, 0.26666666666666666, 0.20000000000000000, 0.33734939759036140, 0.50602409638554210, 0.23529411764705882, 0.30588235294117650, 0.36363636363636365, 0.34090909090909090, 0.40909090909090910, 0.28888888888888886, 0.24719101123595505, 0.27956989247311825, 0.27272727272727270, 0.33684210526315790, 0.28571428571428570, 0.27368421052631580, 0.27083333333333330, 0.31250000000000000, 0.31250000000000000, 0.30927835051546393, 0.25531914893617020, 0.31460674157303370, 0.47311827956989250, 0.85714285714285710, 1.00000000000000000, 1.00000000000000000, 0.82222222222222220, 0.54736842105263160, 0.48421052631578950},
		{0.25000000000000000, 0.24096385542168675, 0.23809523809523808, 0.27586206896551724, 0.21176470588235294, 0.23529411764705882, 0.35294117647058826, 0.41463414634146340, 0.21951219512195122, 0.32941176470588235, 0.23809523809523808, 0.20930232558139536, 0.26666666666666666, 0.20000000000000000, 0.33734939759036140, 0.50602409638554210, 0.23529411764705882, 0.30588235294117650, 0.36363636363636365, 0.34090909090909090, 0.40909090909090910, 0.28888888888888886, 0.24719101123595505, 0.27956989247311825, 0.27272727272727270, 0.33684210526315790, 0.28571428571428570, 0.27368421052631580, 0.27083333333333330, 0.31250000000000000, 0.31250000000000000, 0.30927835051546393, 0.25531914893617020, 0.31460674157303370, 0.47311827956989250, 0.85714285714285710, 1.00000000000000000, 1.00000000000000000, 0.82222222222222220, 0.54736842105263160, 0.48421052631578950},
		{0.28205128205128205, 0.27160493827160490, 0.24390243902439024, 0.30588235294117650, 0.24096385542168675, 0.24096385542168675, 0.40963855421686746, 0.42500000000000000, 0.25000000000000000, 0.38554216867469880, 0.24390243902439024, 0.23809523809523808, 0.27272727272727270, 0.22727272727272727, 0.37037037037037035, 0.49382716049382713, 0.26506024096385544, 0.36144578313253010, 0.41860465116279070, 0.39534883720930230, 0.46511627906976744, 0.34090909090909090, 0.27586206896551724, 0.30769230769230770, 0.30232558139534880, 0.38709677419354840, 0.31460674157303370, 0.30107526881720430, 0.29787234042553190, 0.34042553191489360, 0.34042553191489360, 0.33684210526315790, 0.26086956521739130, 0.34482758620689660, 0.52747252747252750, 0.85393258426966290, 0.82222222222222220, 0.82222222222222220, 1.00000000000000000, 0.60215053763440860, 0.53763440860215050},
		{0.38554216867469880, 0.34883720930232560, 0.29885057471264370, 0.37777777777777777, 0.31818181818181820, 0.31818181818181820, 0.52272727272727270, 0.44705882352941180, 0.30588235294117650, 0.40909090909090910, 0.27586206896551724, 0.24719101123595505, 0.25806451612903225, 0.25806451612903225, 0.67441860465116280, 0.46511627906976744, 0.31818181818181820, 0.40909090909090910, 0.46153846153846156, 0.46153846153846156, 0.72527472527472530, 0.36559139784946240, 0.36956521739130430, 0.35416666666666670, 0.37362637362637363, 0.38775510204081630, 0.38297872340425530, 0.32653061224489793, 0.30303030303030304, 0.34343434343434340, 0.34343434343434340, 0.32000000000000000, 0.26804123711340205, 0.43478260869565216, 0.54166666666666660, 0.59574468085106380, 0.54736842105263160, 0.54736842105263160, 0.60215053763440860, 1.00000000000000000, 0.73469387755102040},
		{0.69879518072289160, 0.51162790697674420, 0.48275862068965520, 0.62222222222222220, 0.59090909090909090, 0.50000000000000000, 0.77272727272727270, 0.47058823529411764, 0.47058823529411764, 0.52272727272727270, 0.43678160919540230, 0.40449438202247190, 0.36559139784946240, 0.38709677419354840, 0.44186046511627910, 0.46511627906976744, 0.38636363636363635, 0.40909090909090910, 0.72527472527472530, 0.72527472527472530, 0.46153846153846156, 0.60215053763440860, 0.63043478260869570, 0.60416666666666660, 0.63736263736263730, 0.59183673469387750, 0.63829787234042560, 0.55102040816326530, 0.40404040404040403, 0.54545454545454540, 0.54545454545454540, 0.40000000000000000, 0.41237113402061853, 0.69565217391304350, 0.66666666666666660, 0.55319148936170210, 0.48421052631578950, 0.48421052631578950, 0.53763440860215050, 0.73469387755102040, 1.00000000000000000}}
	// 节点名称
	CAS  = []string{"63-05-8", "897-06-3", "560-62-3", "510-64-5", "382-45-6", "1035-69-4", "58-22-0", "521-18-6", "734-32-7", "434-22-0", "5173-46-6", "21800-83-9", "53067-82-6", "7370-08-3", "53-43-0", "481-29-8", "53-16-7", "50-28-2", "302-97-6", "57-83-0", "145-13-1", "516-15-4", "434-03-7", "1097-51-4", "604-09-1", "50-22-6", "152-58-9", "53-06-5", "53-03-2", "50-23-7", "566-35-8", "50-24-8", "595-33-5", "66512-11-6", "71658-22-5", "434-13-9", "474-25-9", "128-13-2", "83-49-8", "57-88-5", "601-57-0"}
	medi *Node // 可复用的树堆节点
)

// 获取一个可以用的树堆节点（优先从缓存获取）
func get() *Node {
	if medi == nil {
		return new(Node)
	}
	p := medi
	medi = p.B
	p.B = nil
	return p
}

// 缓存一个树堆节点方便复用
func put(p *Node) {
	p.B = medi
	p.L = nil
	p.R = nil
	medi = p
}

// 维护树堆（保持T字段升序，维护D字段最小堆）
func (this *Heap) maintain(p, q *Node) {
	for q != nil {
		if q.D <= p.D {
			if q.T > p.T { // 这里维护的条件和插入的条件必须完全一致！
				q.L = p
			} else {
				q.R = p
			}
			p.B = q
			break
		}
		p.B, q.B = q.B, p
		if q.T > p.T { // 这里维护的条件和插入的条件必须完全一致！
			q.L, p.R = p.R, q
			if q.L != nil {
				q.L.B = q
			}
		} else {
			q.R, p.L = p.L, q
			if q.R != nil {
				q.R.B = q
			}
		}
		q = p.B
	}
	if q == nil {
		this.Node = p
	}
}

// 完成，即树堆中所有距离信息都被利用完毕
func (this *Heap) Empty() bool {
	return this.Node == nil
}

// 插入距离信息
func (this *Heap) Push(s Distance) {
	var p, q *Node
	// 寻找插入位置
	for p = this.Node; p != nil; {
		if q = p; p.T > s.T { // 这里维护的条件和插入的条件必须完全一致！
			p = p.L
		} else {
			p = p.R
		}
	}
	// 插入节点
	p = get()
	p.Distance, p.B = s, q
	if q != nil {
		if q.T > s.T { // 这里维护的条件和插入的条件必须完全一致！
			q.L = p
		} else {
			q.R = p
		}
	}
	this.maintain(p, q)
}

// 插入距离信息，对目的节点一致的距离信息只保留最短的
func (this *Heap) Update(s Distance) {
	var p, q *Node
	// 寻找插入位置
	for p = this.Node; p != nil; {
		if p.T == s.T {
			break
		}
		if q = p; p.T > s.T { // 这里维护的条件和插入的条件必须完全一致！
			p = p.L
		} else {
			p = p.R
		}
	}
	if p != nil { // 更新节点
		if p.D <= s.D { // 到该节点有更短边，废弃该边
			return
		}
		p.F, p.D = s.F, s.D
	} else { // 插入节点
		p = get()
		p.Distance, p.B = s, q
		if q != nil {
			if q.T > s.T { // 这里维护的条件和插入的条件必须完全一致！
				q.L = p
			} else {
				q.R = p
			}
		}
	}
	this.maintain(p, q)
}

// 提取当前图节点集与外部图节点的最短距离信息
func (this *Heap) Pop() Distance {
	var (
		p, l, r *Node
		q       **Node
		d       Distance
	)
	q = &this.Node
	p = this.Node
	if p != nil { // 旋转至成为叶节点后取出
		for l, r = p.L, p.R; l != nil || r != nil; {
			if l != nil && (r == nil || l.D < r.D) {
				p.L, l.R = l.R, p
				if p.L != nil {
					p.L.B = p
				}
				l.B, p.B = p.B, l
				*q, q = l, &l.R
				l = p.L
			} else {
				p.R, r.L = r.L, p
				if p.R != nil {
					p.R.B = p
				}
				r.B, p.B = p.B, r
				*q, q = r, &r.L
				r = p.R
			}
		}
		*q, d = nil, p.Distance
		put(p)
	}
	return d
}

// 将结构中所有树堆节点均取消指针释放，清空图节点集的字典记录
func (this *Heap) Clean() {
	var p, q *Node
	p = this.Node
	for p != nil {
		if p.L != nil {
			q, p.L = p.L, nil
			q.B, p.B = p.B, q
		}
		if p.R != nil {
			q, p.R = p.R, nil
			q.B, p.B = p.B, q
		}
		q, p = p, p.B
		q.B = nil
	}
}

// 用于实现节点集合（特性：元素总数有限而可预期，方便合并）
// 数组中下标N的元素，其值M如果小于N，则表示M、N属于同一集合
// 同样的，下标M的元素的值也可以指向更小的元素，直至某个元素
// 下标与值相等因此合并两个集合时，只需追溯两条集合链条至头部
// 最小元素，然后将其中下标较大的元素的值设定为较小的那个下标，
// 便可方便实现集合的合并
type Set []int

//创建一个节点集的总集，因为每个元素都等于下标，即都是单元素集合/链条
func NewSet(n int) Set {
	this := make([]int, n)
	for n--; n >= 0; n-- {
		this[n] = n
	}
	return this
}

// 追溯某个集合，直至头部，头部的下标即表示集合的标识符
func (this Set) Trace(n int) int {
	p, q := n, this[n]
	for ; q < n; q = this[n] {
		n = q
	}
	this[p] = n // 此操作是为了在扁平化追溯链条，在节点数量较大时节省查询时间
	return n
}

// 合并两个集合，注意需保证i, j均为Trace返回的头部元素（下标）
func (this Set) Merge(i, j int) {
	if i < j {
		this[j] = i
	} else {
		this[i] = j
	}
}

// Prim算法
func Prim() {
	var (
		have [N]byte // 用来记录节点的集合
		tree Heap
		i, j int
	)
	for {
		have[i] = 1
		for j = 0; j < N; j++ { // 无向图可只需考虑一半，否则需要全部考虑
			if have[j] == 0 {
				tree.Update(Distance{
					i,
					j,
					1 - MTX[i][j],
				})
			}
		}
		if tree.Empty() {
			break
		}
		d := tree.Pop()
		i = d.T
		fmt.Printf("%-2d -> %2d: %.4f\n", d.F, d.T, d.D)
	}
	tree.Clean()
}

// Kruskal算法
func Kruskal() {
	tree := Heap{}
	set := NewSet(N)
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ { // 无向图可只需考虑一半，否则需要全部考虑
			if i == j {
				continue
			}
			tree.Push(Distance{
				i,
				j,
				1 - MTX[i][j],
			})
		}
	}
	for !tree.Empty() {
		d := tree.Pop()
		f := set.Trace(d.F)
		t := set.Trace(d.T)
		if f != t {
			fmt.Printf("%-2d => %2d: %.4f\n", d.F, d.T, d.D)
			set.Merge(f, t)
		}
	}
	tree.Clean()
}

// Kruskal和Prim的“杂交”算法
func Hybrid() {
	tree := [N]Heap{}
	set := NewSet(N) // 	节点集合
	// 每个图节点创建一个边集合
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ { // 无向图可只需考虑一半，否则需要全部考虑
			if i == j {
				continue
			}
			tree[i].Push(Distance{
				i,
				j,
				1 - MTX[i][j],
			})
		}
	}
	for i := N - 1; i > 0; i-- {
		I := tree[i]
		d := I.Pop()
		j := set.Trace(d.T)
		J := tree[j]
		set.Merge(i, j)
		fmt.Printf("%-2d >> %2d: %.4f\n", d.F, d.T, d.D)
		p := Heap{}
		for !I.Empty() {
			d := I.Pop()
			if set.Trace(d.T) != j {
				p.Push(d)
			}
		}
		for !J.Empty() {
			d := J.Pop()
			if set.Trace(d.T) != j {
				p.Push(d)
			}
		}
		tree[i] = Heap{} // 清除悬空指针
		tree[j] = p
	}
}

func main() {
	Prim()
	Kruskal()
	Hybrid()
}