最小生成树问题
- 格式：doc
- 大小：1.39 MB
- 文档页数：30
下载文档原格式
合集下载
因为贪心而失败的例子
因为贪心而失败的例子贪心算法是一种常用的解决问题的算法思想，它通常在每一步选择中都采取当前状态下最好或最优的选择，从而希望最终能够达到全局最优的结果。
然而，贪心算法的贪心选择可能会导致最终结果并非全局最优，而是局部最优或者根本无法得到可行解。
因此，贪心算法在某些问题上会因为贪心而失败。
下面将列举10个因为贪心而失败的例子。
1. 颜色分配问题：假设有n个节点需要着色，并且相邻的节点不能具有相同的颜色。
贪心算法选择每次都选择可用颜色最少的节点进行着色。
然而，这种贪心选择可能会导致最终无法着色所有节点，因为后续节点的颜色选择受到前面节点的限制。
2. 找零问题：假设需要找零的金额为m，而只有面额为1元、5元、10元的硬币。
贪心算法选择每次都选择面额最大的硬币进行找零。
然而，在某些情况下，贪心选择可能会导致找零的硬币数量不是最小的。
3. 最小生成树问题：在一个连通图中，选择一些边构成一个树，使得这些边的权值之和最小，同时保证图中的所有节点都能够通过这些边连通。
贪心算法选择每次都选择权值最小的边加入到树中。
然而，这种贪心选择可能会导致最终得到的树不是最小生成树。
4. 背包问题：给定一组物品，每个物品有自己的重量和价值，在给定的背包容量下，选择一些物品放入背包中，使得背包中物品的总价值最大。
贪心算法选择每次都选择单位重量价值最大的物品放入背包中。
然而，在某些情况下，贪心选择可能会导致最终得到的背包价值不是最大的。
5. 最短路径问题：在一个有向图中，找到两个节点之间的最短路径。
贪心算法选择每次都选择距离最近的节点进行扩展。
然而，这种贪心选择可能会导致最终得到的路径不是最短的。
6. 任务调度问题：给定一组任务，每个任务有自己的开始时间和结束时间，在给定的时间段内，选择一些任务进行调度，使得能够完成尽可能多的任务。
贪心算法选择每次都选择结束时间最早的任务进行调度。
然而，在某些情况下，贪心选择可能会导致最终完成的任务数量不是最多的。
贪心算法通过每次选择局部最优解来达到全局最优
贪心算法通过每次选择局部最优解来达到全局最优贪心算法是一种常用的解决优化问题的算法。
它通过每次选择局部最优解来达到全局最优的目标。
在本文中，我们将介绍贪心算法的原理、应用场景以及优缺点。
一、原理贪心算法的基本原理非常简单：每一步都选择当前状态下的局部最优解，最终得到的结果就是全局最优解。
贪心算法不考虑过去的选择对未来的影响，只关注眼前的最佳选择。
二、应用场景贪心算法在各个领域都有广泛的应用，下面我们将以几个常见的实际问题来说明。
1. 图的最小生成树问题在一个连通无向图中，找到一个包含所有节点且权值最小的无回路子图，这个问题称为最小生成树问题。
贪心算法可以通过每次选择权值最小的边来逐步构建最小生成树。
2. 分糖果问题有一组孩子和一组糖果，每个孩子有一个需求因子和每个糖果有一个大小。
当糖果的大小不小于孩子的需求因子时，孩子可以获得该糖果。
目标是尽可能多地满足孩子的需求，贪心算法可以通过给每个孩子分配满足其需求因子的最小糖果来达到最优解。
3. 区间调度问题给定一个任务列表，每个任务有一个开始时间和结束时间。
目标是安排任务的执行顺序，使得尽可能多的任务能够被完成。
贪心算法可以通过选择结束时间最早的任务来实现最优解。
以上只是一些贪心算法的应用场景，实际上贪心算法可以用于解决各种优化问题。
三、优缺点1. 优点①简单：贪心算法的思路相对简单，容易理解和实现。
②高效：由于只考虑局部最优解，贪心算法的时间复杂度较低，通常能够在较短的时间内得到一个接近最优解的结果。
③可用于近似求解：由于贪心算法不保证得到全局最优解，但可以用于求解近似最优解的问题。
2. 缺点①不保证全局最优解：贪心算法只考虑眼前的最优选择，无法回溯和修正过去的选择，因此不能保证得到全局最优解。
②局部最优解无法转移：在某些情况下，局部最优解并不一定能够转移到全局最优解，导致贪心算法得到的结果偏离最优解。
③对问题的要求较高：由于贪心算法需要找到适合的局部最优解，因此问题必须具备一定的特殊性，而一些问题无法使用贪心算法解决。
曼哈顿距离最小生成树
曼哈顿距离最小生成树曼哈顿距离最小生成树（ManhattanMinimumSpanningTree）是一种在多维空间（N维空间）里寻找最小代价连接任何两个点的有效算法。
它使用曼哈顿距离作为代价并且能够在多维空间中解决最短路径问题。
曼哈顿距离是一种特殊的距离度量，用来测量在一个N维空间中任意两点之间的距离。
它能够很好地表达在有权重约束的多维空间中任意点之间的最短路径。
曼哈顿距离最小生成树以贪心算法的形式实现，能够有效地解决多维空间中的最短路径问题。
它的核心思想是从一个现有的最小生成树开始，不断的增加新的元素来加强和扩展树的结构。
曼哈顿距离最小生成树的基本步骤如下：（1）从空树开始，任意选取一个节点作为初始节点。
（2）以曼哈顿距离为标准，从剩余的n-1个节点中找出与初始节点距离较近的节点，从而构成一个最小生成树。
（3）重复步骤（2），直至最小生成树中包含所有节点，此时得到了一颗曼哈顿距离最小生成树。
曼哈顿距离最小生成树的一个重要特性是它有一个非常直接的应用：它能够帮助我们解决计算最短路径的问题，也就是计算从某个固定起点到任意终点的最短路径。
使用曼哈顿距离最小生成树来计算最短路径的过程如下：（1）先构造一颗曼哈顿距离最小生成树。
（2）对最小生成树中每条边计算曼哈顿距离，并保存到一个表中。
（3）对最小生成树中每个节点，根据曼哈顿距离计算出从起点到该节点的最短距离，并保存到一个表中。
（4）搜索表中最短路径，找到从起点到终点的最短路径，也就是从起点到终点的最短路径。
曼哈顿距离最小生成树在多维空间中解决最短路径问题时，具有非常强大的功能。
它能够快速、高效地找到任意两点之间的最短路径，而无需考虑权重的约束。
这样，它就成为了一种非常有效的最小代价连接算法，在多维空间中广泛应用。
总的来说，曼哈顿距离最小生成树是在多维空间中解决最短路径问题的一种经典算法。
它使用曼哈顿距离作为代价，能够快速、高效地找到任意两点之间的最短路径，而无需考虑权重的约束。
最小生成树问题课程设计
最小生成树问题课程设计一、课程目标知识目标：1. 理解最小生成树的概念，掌握其定义及性质；2. 学会运用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法求解最小生成树问题；3. 了解最小生成树在实际问题中的应用，如网络设计、电路设计等。
技能目标：1. 能够运用普里姆和克鲁斯卡尔算法解决最小生成树问题，并进行算法分析；2. 能够运用所学知识解决实际问题，具备一定的算法设计能力；3. 能够通过合作与交流，提高问题分析和解决问题的能力。
情感态度价值观目标：1. 培养学生对数据结构与算法的兴趣，激发学习热情；2. 培养学生的团队合作意识，学会倾听、尊重他人意见；3. 培养学生面对问题勇于挑战、积极进取的精神。
课程性质：本课程为计算机科学与技术专业的高年级课程，旨在帮助学生掌握图论中的最小生成树问题及其求解方法。
学生特点：学生具备一定的编程基础和图论知识，对算法有一定的了解，但可能对最小生成树问题尚不熟悉。
教学要求：结合学生特点，采用案例教学、任务驱动等方法，注重理论与实践相结合，培养学生的实际操作能力和创新思维。
通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高解决复杂问题的能力。
二、教学内容1. 最小生成树概念与性质- 定义、性质及定理- 最小生成树的构建方法2. 普里姆算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用3. 克鲁斯卡尔算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用4. 最小生成树在实际问题中的应用- 网络设计- 电路设计- 其他领域应用案例5. 算法比较与优化- 普里姆与克鲁斯卡尔算法的比较- 算法优化方法及其适用场景6. 实践环节- 编程实现普里姆和克鲁斯卡尔算法- 分析并解决实际问题- 小组讨论与成果展示教学内容依据课程目标进行选择和组织，注重科学性和系统性。
参考教材相关章节，制定以下教学安排：第1周：最小生成树概念与性质第2周：普里姆算法第3周：克鲁斯卡尔算法第4周：最小生成树在实际问题中的应用第5周：算法比较与优化第6周：实践环节与总结三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言和形象的比喻，对最小生成树的概念、性质、算法原理等基础知识进行讲解，使学生快速掌握课程内容。
最小树问题
i 2在 , X 2 中e 2 选 ,4 边 E 3 E 2 e 2 4e 1,e 2 2,e 3 2,4 3 X X 2 v 4 v 1 ,v 2 ,v 3 ,v 4 ,X 3 v 5 ,v 6 ,
i 3在 , X 3 中e 4 选 ,5 边 E 4 E 3 e 4 5e 1,e 2 2,e 3 2,e 4 4,5 4 X X 3 v 5 v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,X 4 v 6 ,
i 4在 , X 4 中e 5 选 ,6 边 E 5 E 4 e 5 6e 1,e 2 2,e 3 2,e 4 4,e 5 5,6 5 X X 4 v 6 v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 V ,
设v1是T的一个悬挂点，考虑图T-｛v1｝，则图T｛v1｝ 的顶点数为K，由归纳假设可得 ：
，因为 m T(v1) nT(v1)1 nT(v1) nT 1 ， nT(v1) nT 1，则 mT(v1) mT1 ，证毕。
定理3：图T是树的充分必要条件是任意两个顶点之间恰 有一条链。
证明：必要性 因T是连通的，故任两个点之 间至少有一条链。但如果某两个点之间有两条链 的话，那么图T中含有圈，这与树的定义矛盾， 从而任两个点之间恰有一条链。
7
4 v6
5
v4
v2 2
v5
4
3
4 v6 v4
v5
4
3
4 v6 v4
v3 5
6
v1 1
7
5
v2 2
v5
v3 5
4
6
3
v1 1
7
4 v6 5
v4
v2 2
v5
4
3
4 v6 v4
最小生成树问题
2.1 最小生成树
树T(V,E)的性质：
E 树的边数等于其顶点数减“1”，即 V 1 ； 树的任意两个顶点之间恰有一条初级链相连接； 在树中任意去掉一条边后，便得到一个不连通的 图； 在树中任意两个顶点之间添加一条新边，所得新 图恰有一个初级圈。
例如，图 6.4.1 给出的 G1 和 G2 是树，但 G3 和 G4 则不是树。
44
44 69
结果显示于图
求最小生成树的 Prim 算法
Prim 算法的直观描述 假设 T0 是赋权图 G 的最小生成树。任选一 个顶点将其涂红，其余顶点为白点；在一个端 点为红色，另一个端点为白色的边中，找一条 权最小的边涂红，把该边的白端点也涂成红色； 如此，每次将一条边和一个顶点涂成红色，直 到所有顶点都成红色为止。最终的红色边便构 成最小生成树 T0 的边集合。
在求最小生成树的有效算法中，最著名的两个是 Kruskal（克罗斯克尔）算法和 Prim（普瑞姆）算法， 其迭代过程都是基于贪婪法来设计的。 1．求最小生成树的 Kruskal 算法
Kruskal 算法的直观描述 假设 T0 是赋权图 G 的最小生成树，T0 中的边和 顶点均涂成红色，初始时 G 中的边均为白色。 ① 将所有顶点涂成红色； ② 在白色边中挑选一条权值最小的边，使其与红 色边不形成圈，将该白色边涂红； ③ 重复②直到有 n1 条红色边，这 n1 条红色边 便构成最小生成树 T0 的边集合。
最小生成树算法
一个简单连通图只要不是树，其生成树就不唯 一，而且非常多。一般地，n 个顶点地完全图，其 不同地生成树个数为 nn2。因而，寻求一个给定赋 权图的最小生成树，一般是不能用穷举法的。例如， 30 个顶点的完全图有 3028个生成树，3028 有 42 位， 即使用最现代的计算机，在我们的有生之年也是无 法穷举的。所以，穷举法求最小生成树是无效的算 法，必须寻求有效的算法。
最小生成树——城市公交网建设问题
最⼩⽣成树——城市公交⽹建设问题城市公交⽹建设问题【问题描述】 有⼀张城市地图，图中的顶点为城市，⽆向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建⾼速公路的造价，研究后发现，这个地图有⼀个特点，即任⼀对城市都是连通的。
现在的问题是，要修建若⼲⾼速公路把所有城市联系起来，问如何设计可使得⼯程的总造价最少？【输⼊格式】n（城市数，1<=n<=100） e（边数） 以下e⾏，每⾏3个数i,j,wij，表⽰在城市i,j之间修建⾼速公路的造价。
【输出格式】 n-1⾏，每⾏为两个城市的序号，表明这两个城市间建⼀条⾼速公路。
【输⼊样例】 5 8 1 2 2 2 5 9 5 4 7 4 1 10 1 3 12 4 3 6 5 3 3 2 3 8【输出样例】 1 2 2 3 3 4 3 51 #include<iostream>2 #include<cstdio>3 #include<cstring>4using namespace std;56const int maxn=0x7f;7bool visit[101];8int dis[101];9int map[101][101];10int n,m,u,v,h,k;11int min1;1213void sc(int s)14 {15for(int i=1;i<=n;i++)16 dis[i]=map[s][i];17 visit[s]=true;18 dis[s]=0;19for(int i=1;i<=n;i++)20 {21 min1=maxn;22 k=s;23for(int j=1;j<=n;j++)24 {25if(!visit[j]&&dis[j]<min1)26 {27 min1=dis[j];28 k=j;29 }30 }31 visit[k]=1;32for(int j=1;j<=n;j++)33 {34if(!visit[j]&&map[k][j]<dis[j])35 dis[j]=map[k][j];36 }37 }38for(int i=1;i<=n;i++)39for(int j=1;j<=n;j++)40if(map[i][j]==dis[j])41 cout<<i<<""<<j<<endl;42 }4344int main()45 {46 cin>>n>>m;47 memset(map,maxn,sizeof(map)); 48for(int i=1;i<=m;i++)49 {50 cin>>u>>v>>h;51 map[u][v]=map[v][u]=h;52 }53for(int i=1;i<=m;i++)54 dis[i]=maxn;55 sc(1);56return0;57 }。
国家集训队2004论文集_汪汀
证明：⑴必要性 设 T 是最小 k 度限制生成树，则Ⅰ,Ⅱ显然成立。 以下证明 Ⅲ：由Ⅰ,Ⅱ
可知如果(+a1,-b2)和(+a2,-b1)都是 T 的可行交换，则有ω(b2)≤ω(a1),ω(b1)≤ω (a2)，故ω(b1)+ω(b2)≤ω(a1)+ω(a2); 否则，或者(+a1,-b2)或者(+a2,-b1)不是 T 的 可行交换，根据引理 1，T’=T+{a1,a2}-{b1,b2}仍然是 T 的 k 度限制生成树，则ω (T)≤ω(T’),故ω(b1)+ω(b2)≤ω(a1)+ω(a2)。 ⑵充分性
综上，求最小 k 度限制生成树算法总的时间复杂度为 O(Vlog2V+E+kV)。
3、次小生成树
3.1、次小生成树的定义
设 G=(V,E,w)是连通的无向图，T 是图 G 的一个最小生成树。如果有另一棵树 T1，满 足不存在树 T’,ω（T’）<ω（T1） ，则称 T1 是图 G 的次小生成树。
3.2、求解次小生成树的算法
通过上述定理，我们就有了解决次小生成树问题的基本思路。 首先先求该图的最小生成树 T。时间复杂度 O(Vlog2V+E) 然后，求 T 的邻集中权值和最小的生成树，即图 G 的次小生成树。 如果只是简单的枚举，复杂度很高。首先枚举两条边的复杂度是 O(VE)，再判断该交换是否 可行的复杂度是 O(V)，则总的时间复杂度是 O(V2E)。这样的算法显得很盲目。经过简单的 分析不难发现，每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能 保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。我们可以 以此将复杂度降为 O(VE)。这已经前进了一大步，但仍不够好。 回顾上一个模型——最小度限制生成树，我们也曾面临过类似的问题，并且最终采用动态规 划的方法避免了重复计算，使得复杂度大大降低。对于本题，我们可以采用类似的思想。首 先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在
可知如果(+a1,-b2)和(+a2,-b1)都是 T 的可行交换，则有ω(b2)≤ω(a1),ω(b1)≤ω (a2)，故ω(b1)+ω(b2)≤ω(a1)+ω(a2); 否则，或者(+a1,-b2)或者(+a2,-b1)不是 T 的 可行交换，根据引理 1，T’=T+{a1,a2}-{b1,b2}仍然是 T 的 k 度限制生成树，则ω (T)≤ω(T’),故ω(b1)+ω(b2)≤ω(a1)+ω(a2)。 ⑵充分性
综上，求最小 k 度限制生成树算法总的时间复杂度为 O(Vlog2V+E+kV)。
3、次小生成树
3.1、次小生成树的定义
设 G=(V,E,w)是连通的无向图，T 是图 G 的一个最小生成树。如果有另一棵树 T1，满 足不存在树 T’,ω（T’）<ω（T1） ，则称 T1 是图 G 的次小生成树。
3.2、求解次小生成树的算法
通过上述定理，我们就有了解决次小生成树问题的基本思路。 首先先求该图的最小生成树 T。时间复杂度 O(Vlog2V+E) 然后，求 T 的邻集中权值和最小的生成树，即图 G 的次小生成树。 如果只是简单的枚举，复杂度很高。首先枚举两条边的复杂度是 O(VE)，再判断该交换是否 可行的复杂度是 O(V)，则总的时间复杂度是 O(V2E)。这样的算法显得很盲目。经过简单的 分析不难发现，每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能 保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。我们可以 以此将复杂度降为 O(VE)。这已经前进了一大步，但仍不够好。 回顾上一个模型——最小度限制生成树，我们也曾面临过类似的问题，并且最终采用动态规 划的方法避免了重复计算，使得复杂度大大降低。对于本题，我们可以采用类似的思想。首 先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在
组合优化问题求解方法及其应用
组合优化问题求解方法及其应用组合优化问题是指在一定的约束条件下，在一组可选的元素中选取最优组合的问题。
如何求解组合优化问题一直是计算机科学中的重要研究方向之一。
在实际中，组合优化问题的应用非常广泛，从生产调度到金融风险评估等领域都发挥着重要作用。
本文将介绍几种常见的组合优化问题求解方法及其应用。
一、贪心算法贪心算法是一种简单而常用的求解策略。
它通常从问题的某一个初始状态开始，按照某种局部最优的规则逐步构造问题最终的解，直到满足整个问题的全局最优性。
贪心算法的核心思想就是：每一步都做出一个最优决策，最终达到全局最优解。
贪心算法适用于那些带有最优子结构性质的问题。
所谓最优子结构性质是指：一个问题的最优解包含其子问题的最优解。
比如，在背包问题中，每次选择价值最大的物品来装入背包，就是一种贪心策略。
应用场景：1. 最小生成树问题最小生成树问题是指在一个连通的带权图中选取一棵生成树，使得所有边权之和最小。
Kruskal算法和Prim算法均属于贪心算法，可以高效地求解最小生成树问题。
2. 背包问题背包问题是指在有限的背包容量下，如何装入最有价值的物品。
贪心策略可以用来求解部分背包问题和分数背包问题。
二、分支限界法分支限界法是一种基于搜索的求解策略。
它通过不断缩小问题解空间，逐步约束问题的规模，最终求得最优解。
具体来说，分支限界法将问题解空间分成一个个子空间，在选择某一子空间的同时，通过对该子空间的搜索和剪枝，逐渐减小问题解空间的规模，直到找到最优解。
应用场景：1. 旅行商问题旅行商问题是指在一张带权完全图中，如何找到一条经过所有顶点的最短路径。
分支限界算法是一种高效的求解方法，通过剪枝技术可以显著降低搜索空间。
2. 整数规划问题整数规划问题是指在满足各种限制条件下，找到一组整数变量的最优取值使得目标函数值最小或最大。
分支限界算法可以用来求解整数规划的松弛线性规划问题。
三、动态规划算法动态规划算法是一种基于记忆化搜索的求解策略。
最小生成树 课程思政
最小生成树课程思政最小生成树是图论中的一个重要概念，也是计算机科学中的常用算法之一。
它在实际应用中有着广泛的意义，不仅可以用于网络设计、通信传输等领域，也可以用于社交网络分析、物流规划等问题的求解。
本文将以“最小生成树”为主题，探讨其概念、应用和算法实现等方面。
第一部分：概念介绍最小生成树是指在一个连通无向图中，找出一个子图，使得该子图包含原图的所有顶点，且边的权重之和最小。
换言之，最小生成树是连接所有顶点的一棵树，并且树的边的权重之和最小。
第二部分：应用领域最小生成树在实际应用中有着广泛的用途。
首先，它可以用于网络设计。
在计算机网络中，最小生成树可以帮助我们选择一些关键节点，以便构建一个高效的网络拓扑结构，从而提高网络的传输效率和稳定性。
其次，最小生成树还可以用于物流规划。
在物流领域，我们需要确定一些关键的物流节点，以便降低物流成本和提高物流效率。
此外，最小生成树还可以用于社交网络分析。
通过构建一个社交关系的图模型，并应用最小生成树算法，我们可以找出社交网络中的核心节点，从而更好地理解和分析社交关系的结构和特征。
第三部分：算法实现在实际应用中，我们可以使用多种算法来求解最小生成树问题，如Prim算法和Kruskal算法等。
这些算法的基本思想是通过不断地选择权重最小的边，并保证边的选择不会形成环路，最终得到最小生成树。
具体而言，Prim算法是一种贪心算法，它从一个初始节点开始，逐步扩展最小生成树的边，直到包含所有节点为止。
Kruskal 算法则是基于边的排序和并查集等数据结构来实现的，它按照边的权重从小到大的顺序逐个选择边，并保证边的选择不会形成环路。
第四部分：最小生成树的优势和局限性最小生成树作为一种图论中的重要概念和算法，具有以下优势：首先，它能够帮助我们找到一个连通图的最优子图，从而减少了冗余的边和节点，使得网络更加紧凑和高效。
其次，最小生成树可以帮助我们发现网络中的关键节点和连接关系，为网络优化和改进提供了重要的参考依据。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
软件综合课程设计最小生成树问题学生成绩管理二〇一四年六月最小生成树问题一、问题陈述最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
存储结构采用多种。
求解算法多种。
二、需求分析1.在n个城市之间建设网络，只需保证连通即可。
2.求城市之间最经济的架设方法。
3.采用多种存储结构，求解算法也采用多种。
三、概要设计1、功能模块图2、功能描述（1) CreateUDG()创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。
（2) Switch()功能选择：给用户提示信息，让用户选择相应功能。
（3) Adjacency_Matrix()建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。
（4) Adjacency_List()建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。
（5) MiniSpanTree_KRSL()kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。
（6) MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。
四、详细设计本次课程设计采用两种存储结构以及两种求解算法。
1、两种存储结构的存储定义如下：typedef struct Arcell{double adj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{char vexs[MAX_VERTEX_NUM]; //节点数组AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前节点数和弧数}MGraph;typedef struct Pnode //用于普利姆算法{ char adjvex; //节点double lowcost; //权值}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点{char ch1; //节点1char ch2; //节点2double value;//权值}Knode,Dgevalue[MAX_VERTEX_NUM];2、求解算法采用Prim算法和Kruskal算法。
（1）普里姆算法(Prim)算法普里姆算法(Prim)算法是一种构造性算法，生成最小生成树的步骤如下：初始化U={v}。
以v到其他顶点的所有边为候选边。
重复一下步骤(n-1)次，使得其他(n-1)个顶点被加入到U中。
○1从候选边中挑选权值最小的边加入TE，设该边在V—U中的顶点是vk，将顶点vk加入到U中;○2考察当前V—U中的所有顶点vj ，修改候选边：若(vk,vj)的权值小于原来和vj关联的候选边，则用(vk,vj)取代后者作为候选边。
（2）克鲁斯卡尔(Kruskal)算法克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下：置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T 中每一个顶点都构成一个分量）。
将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T 形成回路，则加入TE，否则舍弃，直到TE中包含(n-1)条边为止。
3、使用的函数int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch);int Minimum(MGraph G,Closedge closedge);void MiniSpanTree_PRIM(MGraph G,char u);void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);函数之间的调用关系图：五、程序代码#include<stdio.h>#include<stdlib.h>#include<iostream.h>#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define MAX 1000typedef struct Arcell{double adj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{char vexs[MAX_VERTEX_NUM]; //节点数组AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前节点数和弧数}MGraph;typedef struct Pnode //用于普利姆算法{char adjvex; //节点double lowcost; //权值}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点{char ch1; //节点1char ch2; //节点2double value;//权值}Knode,Dgevalue[MAX_VERTEX_NUM];int CreateUDG(MGraph & G,Dgevalue & dgevalue);int LocateVex(MGraph G,char ch);int Minimum(MGraph G,Closedge closedge);void MiniSpanTree_PRIM(MGraph G,char u);void Sortdge(Dgevalue & dgevalue,MGraph G);void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);int CreateUDG(MGraph & G,Dgevalue & dgevalue)//构造无向加权图的邻接矩阵{int i,j,k;cout<<"请输入城市个数及其之间的可连接线路数目：";cin>>G.vexnum>>G.arcnum;cout<<"请输入各个城市名称(分别用一个字符代替)：";for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)//初始化数组for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=MAX;}cout<<"请输入两个城市名称及其连接费用(严禁连接重复输入!)："<<endl;for(k=0;k<G.arcnum;++k){cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;i = LocateVex(G,dgevalue[k].ch1);j = LocateVex(G,dgevalue[k].ch2);G.arcs[i][j].adj = dgevalue[k].value;G.arcs[j][i].adj = G.arcs[i][j].adj;}return OK;}int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置{int a ;for(int i=0; i<G.vexnum; i++)if(G.vexs[i] == ch)a=i;return a;}void Adjacency_Matrix(MGraph G) //用邻接矩阵存储数据{int i,j;for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)if(G.arcs[i][j].adj==MAX)cout<<0<<" ";elsecout<<G.arcs[i][j].adj<<" ";cout<<endl;}}void Adjacency_List(MGraph G,Dgevalue dgevalue) //用邻接表储存数据{int i,j;for(i=0;i<G.vexnum;i++){cout<<G.vexs[i]<<"->";for(j=0;j<G.arcnum;j++)if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i]) cout<<dgevalue[j].ch2<<"->";elseif(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i])cout<<dgevalue[j].ch1<<"->";cout<<"\b\b "<<endl;}}void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克鲁斯卡尔算法求最小生成树{int p1,p2,i,j;int bj[MAX_VERTEX_NUM]; //标记数组for(i=0; i<G.vexnum; i++) //标记数组初始化bj[i]=i;Sortdge(dgevalue,G);//将所有权值按从小到大排序for(i=0; i<G.arcnum; i++){p1 = bj[LocateVex(G,dgevalue[i].ch1)];p2 = bj[LocateVex(G,dgevalue[i].ch2)];if(p1 != p2){cout<<" 城市"<<dgevalue[i].ch1<<"与城市"<<dgevalue[i].ch2<<"连接。