c++，无向图最小生成树-Kruskal，为什么输出的不对啊

#include<iostream>
#include<algorithm>
using namespace std;

#define MVNum 100//最大顶点数
#define OK 1
#define ERROR 0
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef int Status;
typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
struct EdgeM
{
    VerTexType Head;
    VerTexType Tail;
    ArcType lowcost;
}Edge[MVNum];
int Vexset[MVNum];
pair <int, int> ans[MVNum];
int LocateVex(AMGraph G, VerTexType u)
{//初始条件：图G存在，u和G中顶点有相同特征
    //操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回-1；
    int i;
    for (i = 0; i < G.vexnum; ++i)
        if (u == G.vexs[i])
            return i;
    return -1;
}
Status CreatUDN(AMGraph& G)
{//采用邻接矩阵表示法，创建无向网G
    int i, j, k,w;
    char v1, v2;
    cout << "请输入总顶点数，总边数：" << endl;
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    cout << "依次输入点的信息:" << endl;
    for (i = 0; i < G.vexnum; ++i)//依次输入点的信息
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; ++i)//初始化邻接矩阵，边的权值均置为0
        for (j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = 0;
    cout << "请分别输入边依附的顶点以及权值：" << endl;
    for (k = 0; k < G.arcnum; ++k)//构建邻接矩阵
    {
        cin >> v1 >> v2>>w;//输入一条边依附的顶点和权值
        i = LocateVex(G, v1);//确定v1和v2在G中的位置，即顶点数组的下标
        j = LocateVex(G, v2);
        G.arcs[i][j] = w;//边<v1,v2>的权值置为w
        G.arcs[j][i] = G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
        Edge[i] = { G.vexs[i], G.vexs[j], w };
    }
    return G.arcnum;
}

bool cmp(const EdgeM& a, const EdgeM& b)
{
    return a.lowcost < b.lowcost;
}

void Sort(AMGraph G)
{
    sort(Edge, Edge + G.arcnum, cmp);
}


void output(AMGraph* G)
{
    int i, j, count = 0;
    for (i = 0; i < G->vexnum; i++)
        cout << "   " << G->vexs[i];
    cout << endl;
    for (i = 0; i < G->vexnum; i++)
    {
        cout << G->vexs[i] << "   ";
        for (j = 0; j < G->vexnum; j++)
        {
            cout << G->arcs[i][j] << "   ";
            count++;
            if (count % G->vexnum == 0)
                cout << endl;
        }
    }
}
void MiniSpanTree(AMGraph& G)
{
    Sort(G);
    int cnt = 0;
    int v1, v2, vs1, vs2;
    for (int i = 0; i < G.vexnum; ++i) 
        Vexset[i] = i;                                             
    for (int i = 0; i < G.arcnum-1; ++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;
            ans[cnt++] = { LocateVex(G, Edge[i].Head), LocateVex(G, Edge[i].Tail) };//c++11标准，c99会警告，分开赋值即可
            for (int j = 0; j < G.vexnum; ++j) {
                if (Vexset[j] == vs2) Vexset[j] = vs1;
            }
        }
    }
}

int main() {
    AMGraph(G);
    CreatUDN(G);
    output(&G);
    MiniSpanTree(G);
    return 0;
}

输出截图发我

• 这篇文章讲的很详细，请看：图的最小生成树之Kruskal算法C/C++代码实现
• 除此之外, 这篇博客: C++ 最小生成树中的  kruskal 算法： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

•         

          kruskal 算法也是一种贪心算法，只不过 Prim 算法是对生成树上的点所连的边贪心，而kruskal 算法是对所有的边进行贪心。

          kruskal 算法的策略是：先把每个节点当成一颗最小生成树，然后按照边权从小到大排序，每次枚举边权最小的边，如果两个点不在同一棵最小生成树中，就将两棵生成树合并，反之则舍弃，直到插入 n-1 条边形成一珂生成树。得到的生成树就是最小生成树。

          kruskal 算法与并查集有惊人的相似，所以建议先学会并查集。

          显然，这种策略是正确的。

          因此，kruskal 算法的时间复杂度是：O(m×log m) 。

          图文解释：

  

   【代码实现】

  int n,m;//n个点，m条边
  int sum,ans;//sum记录连接的边数
  int fa[1000001];//记录其祖先
  struct node//结构体
  {
  	int x;//端点之一
  	int y;//端点之二
  	int w;//边权值
  }a[1000001];
  int cmp(node x,node y)//将数据按照从小到大的顺序排序
  {
  	return x.w<y.w;
  }
  int find(int k)//寻找k的祖先
  {
  	if(fa[k]==k)
  	{
  		return k;
  	}
  	return fa[k]=find(fa[k]);
  }
  for(int i=1;i<=n;i++)//初始化
  {
  	fa[i]=i;
  }
  sort(a+1,a+1+m,cmp);//排序
  for(int i=1;i<=m;i++)//加边
  {
  	int x=find(a[i].x);//找端点之一的祖先
  	int y=find(a[i].y);//找端点之二的祖先
  	if(x!=y)//如果不在同一个集合
  	{
  		fa[y]=x;//合并
  		sum++;//边数加1
  		ans+=a[i].w;//记录边权和
  		if(sum==n-1)//如果边数达到n-1，则寻找完毕
  		{
  			break;/*/跳出循环
  		}
  	} 
  }

          

          小编为大家引入一道经典的 kruskal 的题目，以便大家巩固。

          题目传送名：P2330 [SCOI2005]繁忙的都市

          解题思路：其实这道题不论是用 Prim 还是 kruskal 都很简单，不过这里主要以练习 kruskal 为主要目的，所以，重点讲 kruskal 算法。

          题目要求的是最少的边数和生成树内最大的边权值，边的数量肯定是 n-1 ，最大的边权值也只需要在跑 kruskal 的时候记录即可。

  【代码实现】

  #include<iostream>
  #include<cstdio>
  #include<cmath>
  #include<algorithm>
  #include<map>
  #include<vector>
  #include<string>
  #include<cstring>
  #include<queue>//头文件
  using namespace std;
  int n,m;//n个点，m条边
  int sum,ans;//sum用来记录加入生成树的边的数量，ans用来更新最大的边权值
  int fa[1000001];//记录祖先节点
  struct node//记录每条边的信息
  {
  	int x;
  	int y;
  	int w;//边的权值
  }a[1000001];
  int cmp(node x,node y)//将所有的边按照从小到大的顺序排列
  {
  	return x.w<y.w;
  }
  int find(int k)//寻找祖先元素
  {
  	if(fa[k]==k)
  	{
  		return k;
  	}
  	return fa[k]=find(fa[k]);
  }
  int main()
  {
  	scanf("%d%d",&n,&m);//读入
  	for(int i=1;i<=n;i++)
  	{
  		fa[i]=i;//初始化
  	}
  	for(int i=1;i<=m;i++)//读入
  	{
  		int x,y,w;
  		scanf("%d%d%d",&x,&y,&w);
  		a[i].x=x;
  		a[i].y=y;
  		a[i].w=w;
  	}
  	sort(a+1,a+1+m,cmp);//排序
  	for(int i=1;i<=m;i++)//枚举边
  	{
  		int x=find(a[i].x);//查询a[i].x的祖先
  		int y=find(a[i].y);//查询a[i].y的祖先
  		if(x==y)//如果已经在一个集合中，则忽略
  		{
  			continue;
  		} 
  		fa[x]=y;//合并两个集合
  		sum++;//边数累加
  		ans=max(ans,a[i].w);//更新最大边权值
          if(sum==n-1)//如果生成树中的边数等于n-1，则最小生成树已经生成
          {
              break;//跳出
          }
  	}
  	printf("%d %d\n",sum,ans);//输出
  	return 0;//完结撒花
  }