该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
#include
#include
#include
#define maxlen 10
#define large 999
#define null 0
typedef struct
{
int a[maxlen],b[maxlen],w[maxlen]; /*第k条边的起点终点权值*/
char vexs[maxlen]; /*顶点信息集合*/
int vexnum,arcnum; /*顶点数和边数*/
int arcs[maxlen][maxlen]; /*邻接矩阵*/
}graph;
graph g; /*g为图类型变量*/
graph cre_grah(graph g) /*创建图结构*/
{
int i,j,k,c999; /*设c值999为无穷大*/
for(i0;i
for(j0;j
g.arcs[i][j]c; /*初始化邻接矩阵中的所有元素值为无穷大*/
for(k0;k
{
g.arcs[g.a[k]-1][g.b[k]-1]g.w[k]; /*对邻接矩阵赋值*/
g.arcs[g.b[k]-1][g.a[k]-1]g.w[k];
}
return g; /*返回创建的图*/
}
void prim(graph g) /*用prim算法求最小生成树*/
{
int i,j,k,min;
int lowcost[maxlen]; /*保存权值的数组*/
int closet[maxlen]; /*保存最小生成树结点的数组*/
printf("最小生成树的边为:\n");
for(i1;i
{
lowcost[i]g.arcs[0][i];
closet[i]1;
}
closet[1]0; /*选择顶点1作为出发点*/
j1;
for(i1;i
{
minlowcost[j];
ki;
for(j1;j
if(lowcost[j]
{
minlowcost[j];
kj;
}
printf("(%c,%c),",g.vexs[closet[k]],g.vexs[k]); /*输出权值最小的边*/
closet[k]0;
for(j1;j
if(g.arcs[k][j]
{
lowcost[j]g.arcs[k][j];
closet[j]k;
}
}
}
void main()
{
int i,j,k;
system("CLS");
printf("请输入城市的个数城市间道路的条数:");
scanf("%d,%d",
g.vexnumi;
g.arcnumj;
printf("输入顶点信息(即将各城市进行标号顶点替换)");
for(i0;i
{
getchar();
printf("\n第%d个顶点的信息:",i1);
g.vexs[i]getchar();
}
for(k1;k { printf("\t请输入第%d条边的起点:",k); scanf("%d", printf("\n请输入第%d条边的终点:",k); scanf("%d", printf("\n请输入第%d条边的权值:",k); scanf("%d", } cre_grah(g); prim(g); }