博客

6-2 最小生成树（克鲁斯卡尔算法） (10 分)

试实现克鲁斯卡尔最小生成树算法。

函数接口定义：

void Kruskal(AMGraph G);

其中 G 是基于邻接矩阵存储表示的无向图。

裁判测试程序样例：

#include <stdio.h>

#define MVNum 10

#define MaxInt 32767

typedef struct{


char vexs[MVNum];

int arcs[MVNum][MVNum];

int vexnum,arcnum;

}AMGraph;

struct Evode{


char Head;

char Tail;

int lowcost;

}Edge[(MVNum * (MVNum – 1)) / 2];

int Vexset[MVNum];

void CreateUDN(AMGraph &G);//实现细节隐藏

void Kruskal(AMGraph G);

int main(){


AMGraph G;

CreateUDN(G);

Kruskal(G);

return 0;

}

/* 请在这里填写答案 */

输入样例：

第1行输入结点数vexnum和边数arcnum。第2行输入vexnum个字符表示结点的值，接下来依次输入arcnum行，每行输入3个值，前两个字符表示结点，后一个数表示两个结点之间边的权值。

7 9

0123456

0 1 28

0 5 10

1 2 16

1 6 14

2 3 12

3 6 18

3 4 22

4 5 25

4 6 24

输出样例：

按最小生成树的生成顺序输出每条边。

0->5

2->3

1->6

1->2

3->4

4->5

#include<bits/stdc++.h>
using namespace std;
int cmp(Evode a,Evode b)
{
    return a.lowcost<b.lowcost;
}

int find(char x)//找父亲
{
    int y;
    y = int(x)-int('0');
    while(Vexset[y]!=y)y=Vexset[y];
    return y;
}

int add(char x,char y)//判断是否为同一个父亲，不是就加到一起
{
    if(find(x)==find(y))return 0;
    else
    {
        int fx = find(x);
        int fy = find(y);
        Vexset[fx]=fy;
        return 1;
    }
}

void Kruskal(AMGraph G)
{
    for(int i=0;i<G.vexnum;i++)
    {
        Vexset[int(G.vexs[i])-int('0')]=int(G.vexs[i])-int('0');//开始的父亲就是自己
    }
    
    sort(Edge,Edge+G.arcnum,cmp);//按结构体中路径长短排序
    
    for(int i=0;i<G.arcnum;i++)
    {
        if(add(Edge[i].Head,Edge[i].Tail))
        {
           printf("%c->%c\n",Edge[i].Head,Edge[i].Tail);
        }

    }
}

因为没有在csdn上搜到这题，于是就…

可能因为比较简单吧