最小生成树.docx

实验内容或题目
用Prim算法求最小生成树。
输入网的二维矩阵,输出最小生成树。
实验目的与要求
复习图的存储方法和图的遍历方法。
进一步掌握图的非线性特点、递归特点和动态特征。
利用C或C++语言完成算法和程序设计。
上级调试通过实验程序。
输入数据,并求最小生成树。
给出具体的算法分析,包括时间复杂度和空间复杂度。
撰写实验报告。
实验步骤与源程序
⑴实验步骤:
从具体问题抽象出适当的数学模型
设计求解数学模型的算法
编制、运行并调试程序,直到解决实际问题。
⑵源代码:
#define MAX 30
#define MAXDATA 100
#include <>
#include <>
typedef struct
{
char vexs[MAX];
int edges[MAX][MAX];
int n,e;
}MGraph;
void CreateMGraph(MGraph *G)
{
int i,j,k,h;
char ch1,ch2;
printf("\n\t\t请输入顶点数,边数并按【Enter】键(格式如:5,7): ");
scanf("%d,%d",&(G->n),&(G->e));
for(i=0;i<G->n;i++)
{ getchar();
printf("\n\t\t请输入第%d个顶点并按回车: ",i+1);
scanf("%c",&(G->vexs[i]));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=MAXDATA;
for(k=0;k<G->e;k++)
{ getchar();
printf("\n\t\t请输入第%d条边的端点序号(格式为:i,j):",k+1);
scanf("%c,%c",&ch1,&ch2);
printf("\t\t请输入权值:");
for(i=0;ch1!=G->vexs[i];i++);
for(j=0;ch2!=G->vexs[j];j++);
{
scanf("%d",&h);
G->edges[i][j]=G->edges[j][i]=h;
}
}
printf("\n\t\t已建立起无向图G的邻矩阵存储(100代表无穷大数据)\n\t\t");
for(i=0;i<G->n;i++)
{
for(j=0;j<G->n;j++)
printf("%5d",G->edges[i][j]);
printf("\n\t\t");
}
}
void prim(int g[100][100],int k,int n)
{
int i,j,min,p;
struct
{
int adjvex;
int lowcost;
}closedge[MAX];
for(i=1;i<=n;i++)
if(i!=k)
{
closedge[i].adjvex=k;
closedge[i].lowcost=g[1][i];
}
closedge