实习六
一,实验题目:最小生成树问题
二,实验目的:掌握图的基本概念,利用原理解决设计问题的能力,根据具体问题选取存储结构的能力。
若要在n个城市之间建设通信网络,只需架设n-1条线路即可。以最低的经济代价建设这个通信网,求最小生成树,利用Prim或Kruskal算法,输出生成树中各条边以及其权值,设顶点不超过30个。
三,程序功能层次图:
四,运行结果
五,小结
在做这个程序的时候,虽然遇到一些问题,但最后都被我解决, 自信心上得到比较大的提升,这也是这次实践最大的收获。同时,知识上的收获也是不可忽视的,亲手解决问题的过程也是很好的学习过程,并且积累了一些经验,相信会为以后的学习发展带来非常积极的帮助。
源代码:
#include
#include
#define MaxVertexNum 12
#define MaxEdgeNum 20
#define MaxValue 1000
typedef int Vertextype;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
typedef Vertextype vexlist[MaxVertexNum];
int visited[MaxVertexNum]={0};
struct edgeElem
{int fromvex;
int endvex;
int weight;
};
typedef struct edgeElem edgeset[MaxVertexNum];
void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)
{int i,j,k,w;
printf("输入%d个顶点数据",n);
for(i=0;ia)
{CT[i-1].fromvex=a;
CT[i-1].endvex=i;
CT[i-1].weight=GA[a][i];
}
for(k=1;k
#include
#define MaxVertexNum 12
#define MaxEdgeNum 20
#define MaxValue 1000
typedef int Vertextype;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
typedef Vertextype vexlist[MaxVertexNum];
int visited[MaxVertexNum]={0};
struct edgeElem
{int fromvex;
int endvex;
int weight;
};
typedef struct edgeElem edgeset[MaxVertexNum];
void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)
{int i,j,k,w;
printf("ê?è?%d???¥μ?êy?Y",n);
for(i=0;ia)
{CT[i-1].fromvex=a;
CT[i-1].endvex=i;
CT[i-1].weight=GA[a][i];
}
for(k=1;k