1、此程序为c++程序

2、以下代码可实现手动输入，即去掉代码中的/*...*/注释符，并同时去掉赋值代码段

3、源代码

#include<iostream>

using namespace std;

#define MaxInt 32767

#define MVNum 100

typedef struct

{

       char vexs[MVNum];

       int arcs[MVNum][MVNum];

       int vexnum, arcnum;

}AMGraph;

struct

{

       char Head, Tail;

       int lowcost;

}Edge[MVNum];

int Vexset[MVNum];

void CreateUDN(AMGraph &G);

void MiniSpanTree_Kruskal(AMGraph G);

int LocateVex(AMGraph G, char v);

int main()

{

       AMGraph G;

       char p = ‘y‘;

       while (p == ‘y‘)

       {

              CreateUDN(G);

              MiniSpanTree_Kruskal(G);

              cout << "再次执行请输入：y，不执行请输入：n" << endl;

              cin >> p;

       }

       system("pause");

       return 0;

}

//生成无向图

void CreateUDN(AMGraph &G)

{

       int i, j, k, w;

       char v1, v2;

       /*cout << "请输入顶点数和边数:";

       cin >> G.vexnum >> G.arcnum;

       cout << "请输入顶点:";

       for (i = 0; i < G.vexnum; i++)

       {

              cin >> G.vexs[i];

       }*/

       G.vexnum = 6;

       G.arcnum = 10;

       G.vexs[0] = ‘a‘;

       G.vexs[1] = ‘b‘;

       G.vexs[2] = ‘c‘;

       G.vexs[3] = ‘d‘;

       G.vexs[4] = ‘e‘;

       G.vexs[5] = ‘f‘;

       //初始化

       for (i = 0; i < G.vexnum; i++)

       {

              for (j = 0; j < G.vexnum; j++)

              {

                     G.arcs[i][j] = MaxInt;

              }

       }

       /*for (k = 0; k < G.arcnum; k++)

       {

              cout << "请输入边的起点、终点及权值:";

              cin >> v1 >> v2 >> w;

              Edge[k].Head = v1;

              Edge[k].Tail = v2;

              Edge[k].lowcost = w;

              i = LocateVex(G, v1);

              j = LocateVex(G, v2);

              G.arcs[i][j] = w;

              G.arcs[j][i] = G.arcs[i][j];

       }*/

       Edge[0].Head = ‘a‘;

       Edge[0].Tail = ‘b‘;

       Edge[0].lowcost = 6;

       G.arcs[0][1] = G.arcs[1][0] = 6;

       Edge[1].Head = ‘a‘;

       Edge[1].Tail = ‘c‘;

       Edge[1].lowcost = 1;

       G.arcs[0][2] = G.arcs[2][0] = 1;

       Edge[2].Head = ‘a‘;

       Edge[2].Tail = ‘d‘;

       Edge[2].lowcost = 5;

       G.arcs[0][3] = G.arcs[3][0] = 5;

       Edge[3].Head = ‘b‘;

       Edge[3].Tail = ‘c‘;

       Edge[3].lowcost = 5;

       G.arcs[1][2] = G.arcs[2][1] = 5;

       Edge[4].Head = ‘c‘;

       Edge[4].Tail = ‘d‘;

       Edge[4].lowcost = 5;

       G.arcs[2][3] = G.arcs[3][2] = 6;

       Edge[5].Head = ‘b‘;

       Edge[5].Tail = ‘e‘;

       Edge[5].lowcost = 3;

       G.arcs[1][4] = G.arcs[4][1] = 3;

       Edge[6].Head = ‘c‘;

       Edge[6].Tail = ‘e‘;

       Edge[6].lowcost = 6;

       G.arcs[2][4] = G.arcs[4][2] = 6;

       Edge[7].Head = ‘c‘;

       Edge[7].Tail = ‘f‘;

       Edge[7].lowcost = 4;

       G.arcs[2][5] = G.arcs[5][2] = 4;

       Edge[8].Head = ‘d‘;

       Edge[8].Tail = ‘f‘;

       Edge[8].lowcost = 2;

       G.arcs[3][5] = G.arcs[5][3] = 2;

       Edge[9].Head = ‘e‘;

       Edge[9].Tail = ‘f‘;

       Edge[9].lowcost = 6;

       G.arcs[4][5] = G.arcs[5][4] = 6;

}

//构造最小生成树

void MiniSpanTree_Kruskal(AMGraph G)

{

       int i, j, v1, v2, vs1, vs2;

       for (i = 0; i < G.arcnum - 1; i++)

       {

              for (j = i + 1; j < G.arcnum; j++)

              {

                     if (Edge[i].lowcost >Edge[j].lowcost)

                     {

                            Edge[MVNum] = Edge[i];

                            Edge[i] = Edge[j];

                            Edge[j] = Edge[MVNum];

                     }

              }

       }

       for (i = 0; i < G.vexnum; i++)

       {

              Vexset[i] = i;

       }

       cout << "最小生成树:" << endl;

       for (i = 0; i < G.arcnum; i++)

       {

              v1 = LocateVex(G, Edge[i].Head);

              v2 = LocateVex(G, Edge[i].Tail);

              vs1 = Vexset[v1];

              vs2 = Vexset[v2];

              if (vs1 != vs2)

              {

                     cout << ‘(‘ << Edge[i].Head << ‘,‘ << Edge[i].Tail << ‘)‘ << endl;

                     for (j = 0; j < G.vexnum; j++)

                     {

                            if (Vexset[j] == vs2)

                            {

                                   Vexset[j] = vs1;

                            }

                     }

              }

       }

}

//确定结点下标

int LocateVex(AMGraph G, char v)

{

       int l, i;

       for (l = 0, i = 0; i < G.arcnum; i++)

       {

              if (v == G.vexs[i])

              {

                     l = i;

              }

       }

       return l;

}