#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#define OK 1
#define ERROR 0
#define Max_Int 32726
#define MVNum 100
typedef int Status;
typedef int ArcType;
typedef char VerTexType;
struct ed{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost;//边的权值
}Edge[MVNum];
typedef struct{
VerTexType vex[MVNum];//顶点表
ArcType arc[MVNum][MVNum];//邻接矩阵
int arcnum, vexnum;//顶点数和边数
}AMGraph;
//****************************************
int LocateVex(AMGraph *G, VerTexType v)//下标位置的查找
{
int i;
for (i = 0; i < G->vexnum; i++)
{
if (G->vex[i] == v)
return i;
}
return -1 ;
}
/***************************************
void DispGraph (AMGraph &G)
{
int i , j ;
printf ("~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf ("\n输出邻接矩阵的信息：\n\n");
for (i = 0 ; i<G.arcnum ; i++);
printf ("%9d",G.vex[i]);
printf ("输出邻接矩阵：\n");
for(i=0;i<G.arcnum;i++)
{
for(j=0;j<G.arcnum;j++)
{
if(G.arc[i][j]==Max_Int)
printf("%8s", "0");
else
printf("%8d",G.arc[i][j]);
}
printf("\n");
}
}
//***************************************/
Status CreateUDN(AMGraph *G)//创建无向网
{
printf ("建设 1.上海、2.北京、3.南京、4.扬州、5.南通、6.苏州等 六城市之间的交通线路（数字即为城市代号）：\n");
VerTexType v1, v2;
ArcType w;//w为权值即建设费用
int i, j, k;
printf("输入总城市数、总拟定的路数：");
scanf("%d %d", &G->vexnum, &G->arcnum);
printf("输入各个城市代号值：");
fflush(stdin);
for (i = 0; i < G->vexnum; i++)
{
scanf("%c", &G->vex[i]);
}
for (i = 0; i < G->vexnum; i++)
for (j = 0; j < G->vexnum; j++)
{
G->arc[i][j] = Max_Int; //将各值置位无穷大
}
for (k = 0; k < G->arcnum; k++)
{
fflush(stdin) ;
printf("依次输入相连道路两个城市代号以及建路的费用：");
scanf("%c %c %d", &v1, &v2, &w);
Edge[k].Head = v1;
Edge[k].Tail = v2;
Edge[k].lowcost = w;
i = LocateVex(G, v1);//查找该城市代号在总的数组中的位置
j = LocateVex(G, v2);
G->arc[i][j] = w; //相应的俩城市之间的道路建设费用
G->arc[j][i] = G->arc[i][j];//无向图故而两城市之间道路互通
}
return OK;
}
//*******************************************************
void Sort(AMGraph &G) //将所输入的两城市代码以及建设费用按费用进行排序
{
int i, j, addr;
ArcType min;
ed temp;//定义结构体temp
for (i = 0; i < G.arcnum; i++)
{
min = Edge[i].lowcost; //将第一个权值赋值给min
addr = i;
for (j = i + 1; j < G.arcnum; j++)
{
if (min>Edge[j].lowcost) //不断的比较互换
{
min = Edge[j].lowcost;
addr = j;
}//将最小权值换位到i的位置
}
if (addr != i)//若符合整个结构体进行位置互换
{
temp = Edge[i];
Edge[i] = Edge[addr];
Edge[addr] = temp;
}
}
}
//*******************************************************
void MiniSpanTree_Kruskal(AMGraph &G)//应用Kruskal算法进行建立
{
int i, j,v1,v2,vs1,vs2;//vs1 vs2表示连通分量
int sum=0 , k=0;
int Vexset[MVNum];
ed rets[MVNum] ;
Sort(G);
for (i = 0; i < G.vexnum; ++i)
Vexset[i] = i;
printf ("最经济方案为：\n");
for (i = 0; i < G.vexnum;++i)
{
v1 = LocateVex(&G, Edge[i].Head);//v1为始点的下标
v2 = LocateVex(&G, Edge[i].Tail);//v2为终点的下标
vs1 = Vexset[v1];
vs2 = Vexset[v2];
if (vs1 != vs2)//边的连个顶点分属两个不同的连通分量
{
printf("%c->%c--%d\n", Edge[i].Head, Edge[i].Tail ,Edge[i].lowcost);
for (j = 0; j < G.vexnum; ++j)
if (Vexset[j] == vs2)
Vexset[j] = vs1;
sum += Edge[i].lowcost ;
}
}
printf ("最经济方案费用为：%d\n",sum);
}
int main()
{
AMGraph G;
CreateUDN(&G);
/* DispGraph (G) ;
for (i=0 ; i<G.arcnum ;i++)
for (j=0 ; j<G.arcnum ;j++)
if (G.arc[i][j]==Max_Int)
printf ("0");
else
printf ("%d",G.arc[i][j]);*/
MiniSpanTree_Kruskal(G);
return 0;
}