# GÓC SÁNG TẠO > Khu vực lập trình > Java >  Mình có 1 bài tập Java cần mọi ng giúp !!!

## iseovip1

*Implement the Kruskal algorithm for constructing new airlines-system between cities on maps to shut down as many connections as possible.
Representation of Maps:
For this assignment we will be working with maps, or graphs whose vertices are points in the plane and are connected by edges whose weights are Euclidean distances. Think of the vertices as cities and the edges as roads connected to them. To represent a map in a file (input.txt for test your code in implementation time), we list:
1. The number of vertices and edges (a line).
2. Then, list the vertices (index followed by its x and y coordinates with the same Cartesian coordinate system in km - You may assume that all of the x and y coordinates are integers between 0 and 10,000). Each vertex is on a line and each line has the same size.
3. And then list the edges (each pair of vertices is on a line and each line has the same size). 
Your tasks
Create a java program to do the following tasks:
1. Read from the very big given-map file usa-roads-map.txt with Random Access File to create a new file (named edges-usa-roads-map.txt) whose each line contains a edge of the map with the distance between two cities as following format (3 points):
City-1 City-2 distance
(E.g. 727 728 1000 => distance between cities 727 and 728 is 1000 km)
2. Use merge sort algorithm to sort the result-file above in increase order of distance and save the sorted-file with the name: sorted-edges-usa-roads-map.txt (3 points)
3. Use Kruskal algorithm to create a Minimum Spanning Tree for the USA-Roads-Map given. The result tree is saved in a file named: mst-usa-roads-map.txt with the structure following (4 points):
Number of edges of the tree (line 1)
Edge 1 (e.g. 727 728 1000)
Edge 2 (e.g. 736 778 4000)…
Testing the program
You are given the very big file usa-roads-map.txt represented a map that contains 87,575 intersections and 121,961 roads in the continental United States for testing your program.
Assignment Submission
Information regarding the procedure for submitting the assignment will be provided on CMS. The submission must include the complete code. This is your own work. If you use any code from a book to do any other parts, then the reference must appear. The copy of the others or not-run programs must be zero.*

_Bài tập này hạn cuối là 23h 59' tối mai. Ai rảnh và biết về Java mong giúp đỡ. Cám ơn rất nhiều !!!_

----------

