數據結構之---C語言實現最小生成樹之prim（普裡姆）算法
//最小生成樹之Prim算法
//楊鑫
#include
#include
#define n 6
#define MaxNum 10000 /*定義一個最大整數*/
/*定義鄰接矩陣類型*/
typedef int adjmatrix[n + 1][n + 1]; /*0號單元沒用*/
typedef struct
{
int fromvex, tovex; //生成樹的起點和終點
int weight; //邊的權重
}Edge;
typedef Edge *EdgeNode; //定義生成樹的別名
int arcnum; /*邊的個數*/
/*建立圖的鄰接矩陣*/
void CreatMatrix(adjmatrix GA)
{
int i, j, k, e;
printf(=============================
);
printf(圖中有%d個頂點
, n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(i==j)
{
GA[i][j]=0; /*對角線的值置為0*/
}
else
{
GA[i][j]=MaxNum; /*其它位置的值置初始化為一個最大整數*/
}
}
}
printf(請輸入邊的個數：
);
scanf(%d, &arcnum);
printf(請輸入邊的信息，按照起點，終點，權值的形式輸入：
);
for(k=1;k<=arcnum;k++)
{
scanf(%d,%d,%d,&i,&j,&e); /*讀入邊的信息*/
GA[i][j]=e;
GA[j][i]=e;
}
}
/*初始化圖的邊集數組*/
void InitEdge(EdgeNode GE,int m)
{
int i;
for(i=1;i<=m;i++)
{
GE[i].weight=0;
}
}
/*根據圖的鄰接矩陣生成圖的邊集數組*/
void GetEdgeSet(adjmatrix GA,EdgeNode GE)
{
int i, j, k = 1;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(GA[i][j] !=0 && GA[i][j] != MaxNum)
{
GE[k].fromvex = i;
GE[k].tovex = j;
GE[k].weight = GA[i][j];
k++;
}
}
}
}
/*按升序排列圖的邊集數組*/
void SortEdge(EdgeNode GE,int m)
{
int i,j,k;
Edge temp;
for(i=1;i GE[j].weight)
{
k=j;
}
}
if(k!=i)
{
temp = GE[i];
GE[i]=GE[k];
GE[k]=temp;
}
}
}
/*利用普裡姆算法從初始點v出發求鄰接矩陣表示的圖的最小生成樹*/
void Prim(adjmatrix GA,EdgeNode T)
{
int i,j,k,min,u,m,w;
Edge temp;
/*給T賦初值，對應為v1依次到其余各頂點的邊*/
k=1;
for(i=1;i<=n;i++)
{
if(i!=1)
{
T[k].fromvex=1;
T[k].tovex=i;
T[k].weight=GA[1][i];
k++;
}
}
/*進行n-1次循環，每次求出最小生成樹中的第k條邊*/
for(k=1;k
結果：
