weixin_45608903 2019-12-17 19:16 采纳率: 0%
浏览 317

Kruskal算法实现最小生成树主函数的第一行的aaa就无法输出是为什么

Kruskal算法实现最小生成树主函数的第一行的aaa就无法输出是为什么

#include<stdio.h>
#include<iostream>
#define MaxInt 32767  //表示极大值
#define MVNum 10000    //最大顶点数
using namespace std;
/*创建图*/

int v1,v2,w;
int vs1,vs2;

typedef struct
{
    char vexs[MVNum];//顶点表
    int arcs[MVNum][MVNum];//邻接矩阵
    int vexnum,arcnum;//图的当前点数和边数
}AMGraph;

/*设置一个辅助结构体数组Edge:储存边的信息,包括边的两个顶点信息和权值 */
typedef struct
{
    int a,b;//表示枢纽a和枢纽b
    int time;//两个枢纽之间的修建天数
} Edge;//关键字的类型

/*定义一个辅助数组 */
int Vexset[MVNum];

/*定义一个LocaleVex用来求得V在图G中的位置,及顶点数组的下标 */
int LocaleVex(AMGraph &G,int v)
{
    int m;
    for(m=0;m<G.vexnum;++m)
        if(G.vexs[m]==v)
            return m;
}

/*采用邻接矩阵表示法,创建无向网 */
void CreateUDN(AMGraph &G)
{
    int i,j,k;
    cout<<"请输入交通枢纽的数量和候选隧道的数量"<<endl;
    cin>>G.vexnum>>G.arcnum;//输入总顶点数和总边数,即总枢纽个数和隧道数
    fflush(stdin);
    cout<<"依次输入各个枢纽"<<endl;
    for(i=0; i<G.vexnum; ++i) //依次输入点的信息
    {
        cin>>G.vexs[i];
        fflush(stdin);
    }
    for(i=0; i<G.vexnum; ++i) //初始化邻接矩阵,边的权值    均置为极大值
    {
        for(j=0; j<G.vexnum; ++j)
            G.arcs[i][j]=MaxInt;
    }
    cout<<"请写出每条隧道间对应的枢纽a和枢纽b,以及修建天数"<<endl;
    for(k=0;k<G.arcnum;++k)
    {
        cin>>v1>>v2>>w;   //输入一条边依附的顶点即权值
        i=LocaleVex(G,v1);j=LocaleVex(G,v2); //确定v1和v2在G中的位置,即顶点数组的下标
        G.arcs[i][j]=w;   //边<v1,v2>的权值置为w
        G.arcs[j][i]=G.arcs[i][j]; //置<v1,V2>的对称边<v2,v1>的权值w
    }
}
/* 交换权值 以及头和尾 */
void swapn(Edge *edges, int i, int j)
{
    int temp;
    temp = edges[i].a;
    edges[i].a = edges[j].a;
    edges[j].a = temp;
    temp = edges[i].b;
    edges[i].b = edges[j].b;
    edges[j].b = temp;
    temp = edges[i].time;
    edges[i].time = edges[j].time;
    edges[j].time = temp;
}
/* 对权值进行排序 */
void sort(Edge edges[], AMGraph *G)
{
    for(int i = 0; i < G->arcnum; i++)
    {
        for(int j = i + 1; j < G->arcnum; j++)
        {
            if(edges[i].time > edges[j].time)
                swapn(edges, i, j);
        }
    }
    cout<<"权排序之后的为:"<<endl;
    for (int i = 0; i < G->arcnum; i++)
    {
        cout<<edges[i].a<<edges[i].b<<edges[i].time<<endl;
    }

}
/*生成最小生成树*/
void MiniSpanTree_Kruskal(AMGraph &G)
{
    int i,j,n,m;
    int k=0;
    Edge edges[1000];
    //用来构建边集数组并排序*********************
    for(i = 0; i < G.vexnum - 1; i++)
    {
        for(j = i + 1; j < G.vexnum; j++)
        {
            if(G.arcs[i][j] < MaxInt)
            {
                edges[k].a = i;
                edges[k].b = j;
                edges[k].time = G.arcs[i][j];
                k++;
            }
        }
    }
    sort(edges, &G);
    //*******************************************

    for(i=0;i<G.vexnum;++i)
        Vexset[i]=i;      //初始化数组值为0
    for(i=0;i<G.arcnum;++i)//循环每一条边
    {
        v1=LocaleVex(G,edges[i].a);
        v2=LocaleVex(G,edges[i].b);
        vs1=Vexset[v1];
        vs2=Vexset[v2];
        if(vs1!=vs2)/* 假如vs1与vs2不等,说明此边没有与现有的生成树形成环路 */
        {
            cout<<edges[i].a<<edges[i].b<<"答案:"<<edges[i].time;
            for(j=0;j<G.vexnum;++j)
                if(Vexset[j]==vs2)
                   Vexset[j]=vs1;
        }
    }
}
//打印图
void printGraph(AMGraph g)
{
    int i, j;
    for(i = 0; i < g.vexnum; i++)
    {
        for(j = 0; j < g.vexnum; j++)
        {
           cout<<g.arcs[i][j];
        }
        cout<<endl;
    }
}

int main()
{

    cout<<"aaaaaaaaaa";
    AMGraph G;
    cout<<"*****************修建铁路*****************"<<endl<<endl;
    CreateUDN(G);
    printGraph(G);
    MiniSpanTree_Kruskal(G);
    return 0;
}
  • 写回答

1条回答 默认 最新

  • 关注
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题