最小生成树（Prim算法）的go语言实现（最小堆缓存边长法）

行业解决方案、产品招募中！想赚钱就来传！>>>

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

这里大致说明一下原理：

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

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

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

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

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

package mainimport (\"fmt\")// 两节点间的距离type Distance struct {F, T int     // 起点 终点D    float64 // 距离}// 距离统计树堆的节点结构type Node struct {DistanceB, L, R *Node // 父亲，左子，右子}// 树堆的封装，以目的节点排序，而以距离构建最小堆type Heap struct{ *Node } // 树堆根节点const N = 41var (// 距离矩阵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.649350649350641886930, 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, 01ffa.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.561797752808910008880, 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.0000000000ff20000000, 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.355555555555551ff8557, 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.312502000000000000000, 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 := medimedi = p.Bp.B = nilreturn p}// 缓存一个树堆节点方便复用func put(p *Node) {p.B = medip.L = nilp.R = nilmedi = 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 = qbreak}p.B, q.B = q.B, pif q.T > p.T { // 这里维护的条件和插入的条件必须完全一致！q.L, p.R = p.R, qif q.L != nil {q.L.B = q}} else {q.R, p.L = p.L, qif 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, qif 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, qif 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 *Nodeq       **Noded       Distance)q = &this.Nodep = this.Nodeif 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, pif p.L != nil {p.L.B = p}l.B, p.B = p.B, l*q, q = l, &l.Rl = p.L} else {p.R, r.L = r.L, pif p.R != nil {p.R.B = p}r.B, p.B = p.B, r*q, q = r, &r.Lr = p.R}}*q, d = nil, p.Distanceput(p)}return d}// 将结构中所有树堆节点均取消指针释放，清空图节点集的字典记录func (this *Heap) Clean() {var p, q *Nodep = this.Nodefor p != nil {if p.L != nil {q, p.L = p.L, nilq.B, p.B = p.B, q}if p.R != nil {q, p.R = p.R, nilq.B, p.B = p.B, q}q, p = p, p.Bq.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}return this}// 追溯某个集合，直至头部，头部的下标即表示集合的标识符func (this Set) Trace(n int) int {p, q := n, thisfor ; q < n; q = this {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 byte // 用来记录节点的集合tree Heapi, j int)for {have[i] = 1for j = 0; j < N; j++ { // 无向图可只需考虑一半，否则需要全部考虑7bcif have[j] == 0 {tree.Update(Distance{i,j,1 - MTX[i][j],})}}if tree.Empty() {break}d := tree.Pop()i = d.Tfmt.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 := 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()}