替朋友发的,关于Kruskal算法题目,各位大大们,能否给点意见,不需要能把代码写出来(当然能给出感激不尽,嘿嘿)能给个思路或者伪代码也行,谢谢了!题目和翻译如下:
A complete graph is an undirected graph with an edge between each pair of vertices.
A randomly weighted complete graph is a complete graph in which each edge is assigned a weight which is a random real number uniformly distributed between 0 and 1. Let L(n) be the expected (average) weight sum of the edges in a minimum spanning tree of a randomly weighted complete graph with n vertices.Your tasks are to (i) estimate L(n) and the running time of Kruskal's algorithm (22 points) when n = 10; 100; 150; 200; (ii) Observe the changing trend of the value of L(n) with the growth of n. Justify why this happens (3 points).More precisely, write code using one language such as C, C++, Java, or Python program that does this: For each size of n = 10; 100; 150; 200, generate 50 randomly weighted complete graphs with n vertices and determine the weighted sum of the edges in the minimum spanning trees of the graphs as well as the running times of Kruskal's algorithm (the graph generation time will not be taken into account). Print (i) the average of the weighted sum of the 50 MSTs and the average running time of Kruskal's algorithm for nding the 50 weights; (ii) Explain the changing trend of the value of L(n) with the growth of n.Your program should have the following properties.
1. Do not read any input, Write one line of output for each n, and at most 5 extra lines of explanatory output.
2. Store the graph as a symmetric matrix containing the edge weights.
3. Implement Kruskal's algorithm, using subroutines of Quick Sort and Directed Forest for disjoint sets, you need to implement both of these two subroutines, rather than calling them from the program language library.
随机加权完全图的是一个完整的图,其中每个边缘分配重量是0和1之间的均匀分布的随机实数。
设L(n)为最小生成树里顶点总和的权重,n为边的数量。任务是
1. 用C,C++,JAVA或者Python编写,估算下当n=10,100,150,200的时候生成50个随机加权完成图,估算下最小生成树在Kruskal算法的运行时间。
2. 观察随着n的变化,L(n)的变化趋势。并证明原因。你的程序需要满足下面几点要求。
1. 为每一个n写一行单独的输出,和最多5行的解释。
2. 把这个图保存为对称矩阵,包括所有顶点权重。
3. 使用快速排序和Direct Forest的子程序实现Kruskal算法,不能直接调用库里的方法。
再一次感谢了!
A complete graph is an undirected graph with an edge between each pair of vertices.
A randomly weighted complete graph is a complete graph in which each edge is assigned a weight which is a random real number uniformly distributed between 0 and 1. Let L(n) be the expected (average) weight sum of the edges in a minimum spanning tree of a randomly weighted complete graph with n vertices.Your tasks are to (i) estimate L(n) and the running time of Kruskal's algorithm (22 points) when n = 10; 100; 150; 200; (ii) Observe the changing trend of the value of L(n) with the growth of n. Justify why this happens (3 points).More precisely, write code using one language such as C, C++, Java, or Python program that does this: For each size of n = 10; 100; 150; 200, generate 50 randomly weighted complete graphs with n vertices and determine the weighted sum of the edges in the minimum spanning trees of the graphs as well as the running times of Kruskal's algorithm (the graph generation time will not be taken into account). Print (i) the average of the weighted sum of the 50 MSTs and the average running time of Kruskal's algorithm for nding the 50 weights; (ii) Explain the changing trend of the value of L(n) with the growth of n.Your program should have the following properties.
1. Do not read any input, Write one line of output for each n, and at most 5 extra lines of explanatory output.
2. Store the graph as a symmetric matrix containing the edge weights.
3. Implement Kruskal's algorithm, using subroutines of Quick Sort and Directed Forest for disjoint sets, you need to implement both of these two subroutines, rather than calling them from the program language library.
随机加权完全图的是一个完整的图,其中每个边缘分配重量是0和1之间的均匀分布的随机实数。
设L(n)为最小生成树里顶点总和的权重,n为边的数量。任务是
1. 用C,C++,JAVA或者Python编写,估算下当n=10,100,150,200的时候生成50个随机加权完成图,估算下最小生成树在Kruskal算法的运行时间。
2. 观察随着n的变化,L(n)的变化趋势。并证明原因。你的程序需要满足下面几点要求。
1. 为每一个n写一行单独的输出,和最多5行的解释。
2. 把这个图保存为对称矩阵,包括所有顶点权重。
3. 使用快速排序和Direct Forest的子程序实现Kruskal算法,不能直接调用库里的方法。
再一次感谢了!
解决方案 »
- htmlparser改变html
- jar可以转换成exe吗??
- 自己做的一个图片工具类,运行时正常,但关闭窗口的时候出异常
- 求java开发SNMP的资料或实例,谢谢。
- 搜集好的算法书
- 关于zipinputstream的问题
- 关于转义字符串的小问题!
- 一个线程中的异常问题,对throws关键字理解还不够深刻,请大家指教,附源程序
- 哪位大虾帮忙解决一下困扰我的问题!!!多谢!
- 请问:InputStream is =getClass().getResourceAsStream("/db.properties")中,getResourceAsStream 是什么意思,文件db.properties应该
- 初学Java,请帮我看下这个程序为何点击button没有响应?
- java菜鸟新手一枚,求教此题为啥一直RE
CSDN > CSDN论坛 > 高性能开发 > 数据结构与算法