图（3）最小生成树与最短路径的二维矩阵实现形式

曾经终败给现在 2023-06-09 03:52 13阅读 0赞

2.1 krusal算法  
这是一个构建最小生成树的简单算法：  
设G=(V,E)是一个图，V有n个顶点，则利用krusal构建最小生成树的过程如下：  
（1）初始时选取所有的n个顶点构成孤立点的子图T=\{\}  
（2）将边集E按权值递增的顺序排序，顺序的检查边序列，找到下一条两端点位于T的两个不同联通分量的边e，把e加入T.  
（3）不断连接T的顶点数，直到找到n-1条边将其所有的顶点连接。这些联通分量形成的集合就是一个最小生成树。  
例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]  
“”"

'''
    最小生成树1：kural算法
    0：
    0->1:5,0->2:11,0->3:5
    1:
    1->0:5,1->3:3,1->4:9,1->6:7
    2:
    2->0:11,2->3:7,2->5:6
    3:
    3->0:5,3->1:3,3->2:7,3->6:20
    4:
    4->1:9,4->6:7
    5:
    5->2:6,5->6:8
    6:
    6->1:7,6->3:20,6->4:7,6->5:8
    解析：利用rep实现顶点之间的连通元
    '''
    matrix=[[0,5,11,5,0,0,0],
            [5,0,0,3,9,0,7],
            [11,0,0,7,0,6,0],
            [5,3,7,0,0,0,20],
            [0,9,0,0,0,0,7],
            [0,0,6,0,0,0,8],
            [0,7,0,20,7,8,0]]
    n=len(matrix[0])
    edge=[]
    for i in range(n):
        for j in range(n):
           if matrix[i][j]!=0:
               edge.append([i,j,matrix[i][j]])
    reps=[i for i in range(n)] #一开始所有点为自己数字的编号，即点和点之间数字不一样代表没有联通
    edge.sort(key=lambda x:x[2])
    record=[] #记录边的生成过程
    while edge:
        if len(record)==n-1:
            break
        arr=edge.pop(0)
        start,end,edge_len=arr[0],arr[1],arr[2]
        if reps[start]!=reps[end]:
            pre_end=reps[end]
            reps[end]=reps[start]
            record.append([start,end,edge_len])
            #更新联通元
            #可能出现这种情况，1-2联通 3-4联通，但是1-2 3-4 没有联通 所以2-3是可以加入的
            #但是加入以后我们只改变了2-3的数字，4的编号没有和1-2-3一样，但是4和123是联通的
            for i in range(n):
                if reps[i]==pre_end:
                    reps[i]=reps[start]
    print(record)
    sum_w=sum([i[2] for i in record])
    print('权重之和为'+str(sum_w))

\[\[1, 3, 3\], \[0, 1, 5\], \[2, 5, 6\], \[1, 6, 7\], \[2, 3, 7\], \[4, 6, 7\]\]  
权重之和为35  
(2)同上prim算法

'''
    prim算法，prim算法利用的是最小切分原则，如果有两个图，则两个图之间的
    横截线中最短的横截线便是最小生成树中的一条边
    '''
    matrix=[[0,5,11,5,0,0,0],
            [5,0,0,3,9,0,7],
            [11,0,0,7,0,6,0],
            [5,3,7,0,0,0,20],
            [0,9,0,0,0,0,7],
            [0,0,6,0,0,0,8],
            [0,7,0,20,7,8,0]]
    n=len(matrix[0])
    arr1=[] #记录所有横切面的连线
    arr2=[] #记录最小生成树
    i=0 #初始化顶点
    record=[False for i in range(n)] #记录顶点被访问的记录
    while True:
        if len(arr2)==n-1:
            break
        edge_set=matrix[i] #找到第i条边的集合
        record[i]=True
        for j in range(n):
            #如果顶点的另一边没有被访问过，将其加入横截边 比如0-1已经加入了，1->0不用加入
            if matrix[i][j]!=0 and record[j]==False:
                arr1.append([i,j,matrix[i][j]])
        arr1.sort(key=lambda x:x[2],reverse=True)
        while True:
            #弹出最小边
            edge=arr1.pop()
            start=edge[0]
            end=edge[1]
            if record[end]==False:  #如果这条边开始没有被加入 比如0-1这条边在0这个顶点已经被加入了
                #那么1-0这条边便不用加入
                arr2.append(edge)
                break
        i=end #将下一个顶点加入要寻找的横切边中
    #结果
    [[0, 3, 5], [0, 1, 5], [1, 6, 7], [6, 4, 7], [3, 2, 7], [2, 5, 6]]            
    #
    权重之和=sum([i[2] for i in arr2])           
    arr2
    print("最小生成树的权重之和为："+str(权重之和))

————————————————  
版权声明：本文为CSDN博主「weixin\_41611045」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/weixin\_41611045/article/details/89454839

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20230531/64e030c641b8440cae0f0e0e3c60db24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/1780db797e0a40e4ba03996e36a938fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]: /images/20230531/f59d718d06f446828627a2a44de4bfa4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]: /images/20230531/30c295da3b664b9cb90739c768be6b9a.png