最小生成树.txt

最小生成树的prim算法 是求图中的最短路径的一个重要算法 但是是O(n2)复杂度的一个算法

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

/*typedef struct{
   
   int row;
   int col;
   int weight;
}edge ;

typedef struct{
int Vertices[53];
double edge[53][53];
int numOfEdges;
}AdjMWGraph;

//numOfEdges=2809;



typedef char DataType;
typedef char VerT;*/

typedef struct
{
    int vi,vj;//边的起点，终点
   double weight;//边上的权
}edge;
//图的相邻矩阵
edge T[53];  //记录最小生成树

//Prim算法
void prim(int n,double* adj)
{
int m,v,d;
double min,max=32767;
edge e;
//T的初始化
for(int j=1;j<n;j++)
{
    T[j-1].vi=1;
    T[j-1].vj=j+1;
    T[j-1].weight=*(adj+j-1);
} 
//求第k+1条最小生成树的边
for(int k=0;k<=n;k++)
{
    min=max;
    //在T[k],...T[n-2]中选择权最小的边加入最小生成树
    for(j=k;j<=n;j++)
        if(T[j].weight<min)
        {
            min=T[j].weight;
            m=j;
        }
    //交换T[m]和T[k]
    e=T[m];T[m]=T[k];T[k]=e;
    //v是新加入最小生成树的顶点序号
    v=T[k].vj;
    //修改T[k+1]....T[n-2]
    for(j=k+1;j<n;j++)
    {
        d=*(adj+(v-1)*53+[T[j].vj-2);
        if(d<T[j].weight)
        {
            T[j].weight=d;
            T[j].vi=v;
        }
    }
}

}

void main(void){
	int i;
	/*图的矩阵*/
	double a[53][53]={
		{0  , 0	,     0  ,    0   ,  0   ,    0 ,     0,      0  ,    0    ,  0   ,   0    ,  0  ,    0  ,    0  ,    0  ,    0  ,    0   ,   0   ,   0    ,  0   ,   0    ,  0  ,    0  ,    0  ,    0   ,   0     , 0   ,   0   ,   0   ,   0   ,   0  ,    0    ,  0  ,    0   ,   0 ,  10.3 ,   5.9 ,  11.2  ,    0  ,    0  ,    0  ,    0  ,    0   ,   0   ,   0      ,0    ,  0  ,    0  ,    0   , 6.0  ,   0    , 0 ,    0   },