Kruscal 算法：按边搜索，整体扫描，一词入选-526互联

首先是该算法 Intuitive 参考：

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

数据结构采用的是 Activity on Edge：

1. 图的数据输入

# -------------
# -- Kruscal
# -------------

import numpy as np
import pandas as pd


source = [4,1,1,2,2,5,5,7,7,6,6,4]
destiny = [1,2,3,4,5,4,7,4,6,4,3,3]
weight = [1,2,4,3,10,7,6,4,1,8,5,2]

# -- 这个是错误解答： PRIM 用 AOV 试试
tmp_graph = pd.DataFrame()
tmp_graph['source'] = source
tmp_graph['destiny'] = destiny
tmp_graph['weight'] = weight
tmp_graph['num'] = tmp_graph.index
tmp_graph['tag'] = 0

2.准备所有函数：SWAP值、找出最小的边、判断顶点是否被选入

# -------------
# -- Kruscal
# -------------

# -- SWAP
def swap_val(a, b):
    tmp = a; a = b; b = tmp;
    return a,b

# -- Minimum - return num
def find_min_weight(g_in):
    # -- renew
    tmp_g = g_in.reset_index(drop=True)
    tmp_min = tmp_g['weight'][0]
    tmp_min_ind = tmp_g['num'][0]
    
    for i in range(1,len(tmp_g)):
        if (tmp_g['weight'][i] < tmp_min):
            tmp_min = tmp_g['weight'][i] 
            tmp_min_ind = tmp_g['num'][i]
    
    return tmp_min, tmp_min_ind

# --- Minimum Edge 
# --- Min Vertex Id when same weighted edge
def find_min_edge(g_in):
    tmp_g = g_in.reset_index(drop=True)
    tmp_min_edge=-1; tmp_edge=-1
    tmp_min_edge_id=-1; tmp_edge_id=-1
    
    for i in range(len(g_in)):
        if i==0:
            tmp_min_edge=int(g_in['weight'][i])
            tmp_min_edge_id=int(g_in['num'][i])
        else:
            tmp_edge=int( g_in['weight'][i] )
            tmp_edge_id=int(g_in['num'][i])
            
            if tmp_edge <tmp_min_edge:
                tmp_min_edge, tmp_edge = swap_val(tmp_min_edge, tmp_edge)
                tmp_min_edge_id = tmp_edge_id
                
        #print(tmp_min_edge, tmp_edge, tmp_min_edge_id, tmp_edge_id)
    return tmp_min_edge_id
    
# --- is_vertex_existed
# -- id in bool out
def is_vertex_existed(v_id_in, v_vec_in):
    is_existed=0
    pos_existed=-1
    for i in range(len(v_vec_in)):
        if v_id_in == v_vec_in[i]:
            is_existed=1
            pos_existed=i
            break
            
    return is_existed, pos_existed
     
# ------ 获取节点向量
tmp_vertex = list(tmp_graph['source']) + list(tmp_graph['destiny'])
tmp_vertex = list(set(tmp_vertex))
print(tmp_vertex)

tmp_graph

3. 循环，完成 Kruscal 算法。注意，这里处理的问题包含，连通集问题、回路问题，由于算法本身限制，回路在不属于主要问题，可以由解决连通问题一并解决。

其实，可以解决连通、回路的是并查集，这里为了方便起见，直接用分子集 + TAG 方式解决。

len_remain = len(tmp_graph[tmp_graph.tag==0])  # 未被选入的点
len_mar = len(tmp_graph)
cnt=0

selected_set = pd.DataFrame()
vertex_set=[]
v_subset_1=[]
v_subset_2=[]
is_link_subset=0  # Kruscal 算法，最后一个点加进去之前，已经选入的集合只有两种情况：连通 / 不连通

while(len_remain>0 and cnt>-1 ):
    
    tmp_g_1 = tmp_graph[tmp_graph.tag==0].reset_index(drop=True)

    tmp_id = find_min_edge(tmp_g_1)
    tmp_graph['tag'][tmp_id]=1
    
    tmp_g_2=tmp_graph[tmp_graph.num==tmp_id].reset_index(drop=True)

    dot_1=int(tmp_g_2['source'][0]); 
    dot_2=int(tmp_g_2['destiny'][0]);
    is_existed_1, _ = is_vertex_existed(dot_1, vertex_set)
    is_existed_2, _ = is_vertex_existed(dot_2, vertex_set) 
    
      # --- SUBSET
    is_existed_1_1, _ = is_vertex_existed(dot_1, v_subset_1)
    is_existed_1_2, _ = is_vertex_existed(dot_1, v_subset_2)
    is_existed_2_1, _ = is_vertex_existed(dot_2, v_subset_1)
    is_existed_2_2, _ = is_vertex_existed(dot_2, v_subset_2)  
    subset_tag = 10000 + is_existed_1_1*1000 + is_existed_1_2*100 + is_existed_2_1*10 + is_existed_2_2*1  

    if (is_existed_1==0 or is_existed_2==0):
        if cnt==0:
            selected_set = tmp_g_2
        else:
            selected_set = pd.concat([selected_set, tmp_g_2])
            
        if is_existed_1==0:
            vertex_set.append(dot_1)   
        if is_existed_2==0:
            vertex_set.append(dot_2)               
    else:
          # --- 连接连通集
        if ( (subset_tag == 11001 or subset_tag== 10110) and is_link_subset==0 ):
            is_link_subset=1
            selected_set = pd.concat([selected_set, tmp_g_2])

      # --- subset ---
    if is_existed_1==0 and is_existed_2==0 and cnt>0:
        v_subset_2.append(dot_1)
        v_subset_2.append(dot_2)
    else: 
        if is_existed_1==0:
            v_subset_1.append(dot_1)    
        if is_existed_2==0:
            v_subset_1.append(dot_2)    
                   
    cnt=cnt+1
    len_remain=len(tmp_graph[tmp_graph.tag==0])
    
# --- END: 这种算法一定会少一条边 ---
selected_set = selected_set.reset_index(drop=True)    
selected_set