什么是生成树？
给定一个无向连通图，图的生成树是一棵跨越的树（也就是说，它包括) 并且是（树中的每条边都属于)
什么是最小生成树？
生成树的代价是树中所有边的权重之和。可以有许多生成树。最小生成树是所有生成树中成本最小的生成树。也可以有许多最小生成树。
最小生成树直接应用于网络设计。它用于逼近旅行商问题、多终端最小割问题和最小成本加权完美匹配的算法。其他实际应用包括：
- 聚类分析
- 手写识别
- 图像分割
有两种著名的算法可以找到最小生成树：
克鲁斯卡尔算法
Kruskal 算法通过将边一条一条地添加到不断增长的生成树中来构建生成树。Kruskal 的算法遵循贪心方法，因为在每次迭代中，它会找到一条权重最小的边并将其添加到不断增长的生成树中。
算法步骤：
- 根据权重对图边进行排序。
- 从权重最小的边开始向 MST 添加边，直到权重最大的边。
- 仅添加不形成循环的边，仅连接断开组件的边。
所以现在的问题是如何检查顶点是否连接？
这可以使用从第一个顶点开始的 DFS 来完成，然后检查是否访问了第二个顶点。但是 DFS 会使时间复杂度变大，因为它的阶数为在哪里是顶点的数量，E是边数。所以最好的解决方案是“不相交集”： 不相交集是其交集是空集的集合，因此这意味着它们没有任何共同的元素。
现实生活中的应用
最小生成树用于网络设计（即电话或有线网络）。它们还用于为复杂的数学问题（如旅行商问题）找到近似解。其他不同的应用包括：
- 聚类分析。
- 实时人脸跟踪和验证（即在视频流中定位人脸）。
- 计算机科学中避免网络周期的协议。
- 基于熵的图像配准。
- 最大瓶颈路径。
- 抖动（为数字录音添加白噪声以减少失真）
下面是一个最短路径和最小生成树的java代写案例：
Assignment 3: Shortest Paths and Minimum Spanning Trees
Introduction
The goal of this assignment is to analyze and program some graph algorithms
and visualize them. This assignment includes three tasks.
Task 1 – Shortest Paths
1. A program called DijkstraLabeller.java tries to label the shortest path for a given weighted graph with a starting vertex by harnessing Dijkstra’s algorithm. It may work but not be perfect. Please study this implementation carefully and point out its weakness(es), which can be such as lacking enough information in returned objects, low efficiency etc. When you find out a point, you need to make an in-depth analysis.
For example, assume that this implementation has a low-efficiency issue; you need to specify where they are from, their time complexity, etc.
2. Based on the analysis from the previous step, you need to reimplement this solution to solve these issues. You need to create a new java class named DijkstraLabeller2.java within the package dsa.algorithms. If needed, you can create a few other classes. For example, as we mentioned in our lecture, if you want to use an adaptable priority queue, you may need to create a new interface and its implementation as well. In your solution, you can use java built-in data structures, such as Map, List etc. However, a graph and its edges and vertices must be represented by the classes provided within the assignment.
3. Create a test class named TestDijkstraLabeller.java to check that your solution is correct and make comparisons with the previous solution.
Task 2 – Minimum Spanning Trees
1. A program called KruskalLabeller.java manages to label the minimum spanning tree in a given graph by utilizing Kruskal’s algorithm. Similar to Task 1, please study this implementation carefully and point out its weakness(es), particularly in terms of its efficiency.
2. Based on the analysis from the previous step, you need to reimplement this solution to solve these issues. You need to create a new java class named KruskalLabeller2.java within the package dsa.algorithms. If needed, you can create a few other classes. For example, you may need to implement Union-Find structure. In your solution, you can use java built-in data structures, such as Map, List etc. However, a graph and its edges and vertices must be represented by the classes provided within the assignment.
3. Create a test class named TestKruskalLabeller.java to check that your solution is correct and make comparisons with the previous solution.
Task 3 – Visualization
Visualization can help us to better understand graphs and examine our graph algorithms. This task requires you to study the existing java-based techniques for graph visualization and choose a suitable one to implement a solution to visualize the graphs used in your testing in Trask 2 and Task 3 and demonstrate the process of Dijkstra’s algorithm and Kruskal’s algorithm.
Instructions
• Download the file Assignment3-Source.zip from Brightspace. The contents of this file include DijkstraLabeller.java and KruskalLabeller.java and all their dependent classes.
• When you study the weaknesses of the existing implementations, you need to record these weaknesses and your analysis in your report.
• In your solutions of Task 1 and Task 2, a graph must be represented by IGraph, and its vertices and edges must be represented by IVertex and IEdge, which are defined in dsa.iface package. a Graph implementation: EdgeListGraph is provided in dsa.impl package, you should use it in your testing to hold your graph data.
• You can design your own returned data type to hold any data you need for the next step to visualize graphs.
• This assignment requires you to do some independent research outside of what is directly covered in the lectures. For example, two chapters in Goodrich and Tamassia’s book are suggested to read, i.e., Chapter 9.5 Adaptable Priority Queues, Chapter 14.7.3 Disjoint Partitions and Union-Find Structures. You can learn the solutions provided by these chapters and then make your own solutions.
• When testing your implementation and making comparisons, you should compare their efficiencies at different graphs and record the results and analyze them in your report.
• In the task of visualization, you can use any java-based components.
• You should summarise the studies for graph visualization and briefly depict your solution. It is essential to put critical screenshots of the visualization produced by your program into the report.
Submission
This is an individual assignment. Therefore, all code and the report must be written by yourself. Assignment 1 contained some advice about avoiding plagiarism in programming assignments.
• Submit a zip file to Brightspace, which should include all java files, libraries, and data used in your project. All code should be wellformatted and well-commented to describe what it is trying to do.
• Submit a pdf report to Brightspace. This report should be a humanreadable document (i.e., do not simply include code). In your report, it is recommended to have the following essential topics, but not limited:
o Record the weaknesses of the existing implementations and provide your in-depth analyses.
o Depict any tricks (novel or different ideas) used in your solution.
o Document the testing strategies and record results and provide your analyses.
o Include a short literature review about Java-based graph visualization.
o Depict your visualization solution.
o List newly added java classes, and describe their functionalities.
• The pdf file of your report must be submitted as a separate file, i.e., it cannot be compressed into the zip file with your code or data, for the purpose of originality checking.
