数据结构图（下）最小生成树

朱雀 2023-07-08 14:29 115阅读 0赞

## **最小生成树** ##

构造连通图的最小代价生成树

## **普里姆算法Prim** ##

Prim算法用到的是邻接矩阵，具体方法就是构造一个一维数组初始化值位一个特别大的数（再邻接矩阵里面就已经存好值了），然后从起始点开始找与之相连的点，并存到一维数组里面；进行第一轮循环，找出相连点里面权值最小的，标记这个最小值和点的下标，然后遍历一维数组，找出与这个最小权值点相连的点，再把对于权值存到一维数组里面，再重复上面的步骤，直到完全构成一个联通图。  
**代码**  
//G是邻接矩阵,n为点数目

void Prim(int G[][],int n)
    { 
       int min,i,j;
       int a[1010];//存相关顶点下标
       int low [1010];//一维数组存权值
       low[0]=0;
       for(int i=1;i<n;i++)
       { 
           low[i]=G[0][i];
           a[i]=0;
        }
        for(int i=1;i<n;i++)
        { 
           min=-9999;
           j=1;
           k=0;
           while(j<n)
           { 
           if(low[j]!=0&&low[j]<min)
           { 
              min=j;k=j;
           }
           j++;
           }
           low[k]=0;
           for(j=1;j<n;j++)
           { 
             if(!low[i]&&G[k][j]<min)
             { 
             low[j]=G[k][j];
             a[j]=k;
             }
           }
        }
    }

## **克鲁斯卡尔算法Kruskal** ##

Kruskal算法需要把邻接矩阵先转换为一个边集数组，就是按权值递增顺序存的一个结构体数组。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

struct { 
    int s;
    int e;
    int weigh;
    }Edge;
    void Kruskal(int G[][],int n)
    { 
    int i,n,m;
    int parent[1001];
    Edge edges[1010];
    memset(parent,0,sizeof(a));
    for(int i=0;i<n;i++)
    { 
    n=Find(parent,edges[i].s);
    m=Find(parent,edgs[i].e);
    if(n!=m)
    { 
    parent[n]=m;
    printf("%d %d %d",edgs[i].s,edgs[i].e,edgs[i].weight);
    }
    }
    }
    int Find(int *parent,int f)
    { 
    while(parent[f]>0)
    f=parent[f];
    return f;
    }