#define MAXN 30
int set[MAXN];
typedef struct Mintree
{//最小生成树结构体定义
int x, y;
int dis;
}Mintree;
Mintree map[MAXN], mst[MAXN];
bool cmp(const Mintree a,const Mintree b)
system("pause");
system("cls");
printf("请输入城市数量n = ");
}
return 0;
}
四．运行结果与总结
由用户自己输入城市个数n=7，并输入邻接矩阵的上半矩阵的元，即路径代价，最后得到开销最小的通信网络——最小生成树。
可见该题的最小生成树为：
得到最小开销为57。
离散数学大作业
题目：通信城市造价最小问题
姓名：章苗苗
学院：电子工程学院
系：电子工程学院
专业：智能科学与技术
年级：2009级
学号：02095058
老师：李阳阳
问题：
如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值.
{
for (j = i+1; j < n; j++)
{
map[k].x = i;
map[k].y = j;
printf("\n<%-2d,%-2d>\n", map[k].x, map[k].y);
scanf("%d", &map[k].dis);
k++;
}
}
puts("--------------------------------\n");
if (fx != fy)
{//两端点不在一个集合，合并并返回真
if (rank[fx] > rank[fy])
{
set[fy] = fx;
}
else if (rank[fx] < rank[fy])
{
set[fx] = fy;
}
else百度文库
{
set[fx] = fy;
rank[fy]++;
}//按秩合并
}
2：主程序：
int main()
{
初始化；
while (条件)
{
接受命令;
处理命令;
}
return 0;
}
3：抽象数据类型图的定义如下：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：
R={VR}
VR={<v,w>|v，w∈V且P（v，w），<v，w>表示从v到w的弧，
r = set[r];
int i = x, j;
while (i != r)
{
j = set[i];
set[i] = r;
i = j;
}//路径压缩
return r;
}
bool Merge(int x, int y)
{//合并集合函数
int fx = Find(x);
int fy = Find(y);
ans += map[i].dis;//最小生成树的所有边的带权和
printf("\n<%-2d,%-2d>\t%-2d\n", map[i].x, map[i].y, map[i].dis);
num++;
if (num == n-1)
break;
}
}
printf("\n并且最小开销为：%d\n\n",ans);
while(scanf("%d", &n) != EOF)
{
Init(n);
puts("--------------------------------\n");
printf("生成%d条通信网络费用信息：\n", n * (n-1) / 2);
k = 0;
for (i = 0; i < n; i++)
（2）若D-{root}≠ ，则存在D-{root}的一个划分D1，D2，…，Dm（m>0），对任意j≠k（1≤j,k≤m）有Dj∩Dk= ，且对任意的I（1≤i≤m），惟一存在数据元素xi∈Di有<root，xi>∈H；
（3）对应于D-{root}的划分，H-{<root，x1>，…，<roor，xm>}有惟一的一个划分H1，H2，…，Hm（m＞0），对任意j≠k(1≤j，k≤m)有Hj∩Hk= ，且对任意I（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为跟root的子树。
谓词P（v，w）定义了弧<v，w>的意义或信息}
4：抽象数据类型树的定义如下：
ADT Tree{
数据对象D:D是具有相同特性数据元素的集合。
数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否则R={H}，H是如下二元关系：
（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
数据关系：S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n）
Init (n):初始化集合，构造n个集合，每个集合都是单成员，根是其本身。
Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。
Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。
return true;
}
return false;
//两端点原本在一个集合，返回假。
}
int main()
{
int n, i, j, k, num;
int fx, fy;
int ans;
srand((unsigned)time(NULL)); //随机种子函数
printf("请输入城市数量n = ");
一．问题分析
1.可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。
sort(map, map + k, cmp);
//按边从小到大的顺序进行快速排序
ans = 0;
num = 0;
printf("得到开销最小的通信网络如下：\n");
for (i = 0; i <k; i++)
{
if (Merge(map[i].x, map[i].y))
{//边的端点不在一个集合，则合并之
}
5:本程序包括两个模块，调用关系比较简单：
（1）主程序模块
（2）带权无向图模块。
程序各模块之间的调用关系如下：
三．详细设计
#include <cstdio>
#include <ctime>
#include <algorithm>
using namespace std;
#define MOD 101
（6）结束。
4．测试数据
用户自定义输入城市个数，输入结束后回车即显示生成的最小生成树及最小开销。
二．概要设计
1：抽象数据类型MFSet的定义：
ADT MFSet {
数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。
2.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。
3．程序执行的命令包括：
（1）利用克鲁斯卡尔算法求最小生成树。
（2）构造最小生成树中的连通分量。
（3）权值应存放在定义的数组中。
（4）输入城市个数。
（5）输出费用最少的生成树。
{
return a.dis < b.dis;
}//快排比较函数
void Init(int n)
{//初始化为n个集合
int i;
for (i = 0; i < n; i++)
{
set[i] = i;
rank[i] = 0;
}
}
int Find(int x)
{//查找该集合的根
int r = x;
while (set[r] != r)
