文件名称：最小生成树设G=（V，E）是无向图联通带权图，即一个网络。E中每条边（v，w）的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有定点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为最小生成树。采用贪心策略可以直接求得给定网络的最小生成树。
文件大小：1KB
文件格式：RAR
更新时间：2012-03-31 08:49:23
最小生成树
设G=（V，E）是无向图联通带权图，即一个网络。E中每条边（v，w）的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有定点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为最小生成树。采用贪心策略可以直接求得给定网络的最小生成树。 解析请参加教材115页。 实验方法： 使用贪婪法设计本问题的解决方案。 编成任务： 给定网络图，求其最小生成树。 Input 节点个数和给定网络图的邻接矩阵表示方法，其中权值为65535表示两个节点间没有连接。否则数字表示节点间权值。 Output 输出最小生成树包括的节点 Sample Input 11 65535 9 59 69 96 11 72 100 17 43 28 9 65535 40 21 23 61 78 97 41 76 86 59 40 65535 39 48 55 64 11 85 23 44 69 21 39 65535 82 80 62 80 98 8 78 96 23 48 82 65535 70 97 55 2 6 2 11 61 55 80 70 65535 45 71 45 42 45 72 78 64 62 97 45 65535 72 93 89 17 100 97 11 80 55 71 72 65535 97 28 100 17 41 85 98 2 45 93 97 65535 70 77 43 76 23 8 6 42 89 28 70 65535 72 28 86 44 78 2 45 17 100 77 72 65535 Sample Output 106
【文件预览】：
最小生成树
----新建 文本文档.txt(2KB)