Use kruskal algorithm to construct a minimal spanning tree

Assignment Help Computer Graphics
Reference no: EM13867840

Write a program to: 
Read an edge list for an undirected, weighted graph and
1. use Dijkstra's Single Source Shortest Path Algorithm to construct the shortest path from a given vertex S to all other vertices.
2. use Kruskal's algorithm to construct a minimal spanning tree for the graph. 
Input:
The input will begin with a line containing two space-separated integers, N giving the number of vertices in the graph (vertices are numbered 1,2,3,...,N), and S giving the source vertex for Dijkstra's algorithm. Then the edge list will follow. For each graph 
edge there will be a line containing three space-separated integers, vertex, vertex, and weight. The edges are not listed in any particular order.
Here is an example input file:
7 1        // number of vertices and source vertex
1 2 2      // undirected edge from v1 to v2 of weight 2
1 4 1
2 5 10     // undirected edge from v2 to v5 with weight 10
2 4 3
5 7 6      // there will not be comments in the input
3 1 4
3 6 5
4 3 2
7 6 1
4 5 2
4 7 4
4 6 8
0 0 0
There will not be more than 1024 vertices. Edge weights will be in [1, 200]. The edge list will be terminated by a line containing three zeros.
Expected Output:
Use Dijkstra's algorithm to form shortest paths and output the lists of vertices on the shortest paths from the given vertex to all the others as follows:
1 1 0      // shortest path from 1 to 1 has length 0
1 2 2      // this list must be in increasing order of
1 4 3 3    // terminal vertex
1 4 1
1 4 5 3    // shortest path from 1 to 5 is via 4 and has length 3
1 4 7 6 6  // shortest path from 1 to 6 is via 4, 7 and has length 6
1 4 7 5    // do not print these comments
Then print a blank line followed by the minimal spanning tree as follows:
1 2   // each line must begin with the smaller vertex number
1 4   // lines with equal first numbers should be in order of the 
3 4   // second number
3 5
4 5
6 7
Finally print a line giving the total length of the edges in the minimal spanning tree as follows:
Minimal spanning tree length = 13
Sample Input                     |Expected Output
---------------------------------|--------------
7 1                              |1 1 0
1 2 2                            |1 2 2
1 4 1                            |1 4 3 3
2 5 10                           |1 4 1
2 4 3                            |1 4 5 3
5 7 6                            |1 4 7 6 6
3 1 4                            |1 4 7 5
3 6 5                            |
4 3 2                            |1 2
7 6 1                            |1 4
4 5 2                            |3 4
4 7 4                            |3 5
4 6 8                            |4 5
0 0 0                            |6 7
                                 |Minimal Spanning tree length = 13
RULES FOR PROGRAMMING AND SUBMISSION:
1. Your submitted code must be entirely your own. If you do copy code from a text or the web, cite the copied section with a comment. Points could be lost, depending on what is copied.
2. Write your program as one source file and remove the "package" construct from your Java source before submitting. 
3. Name your source file as N1N2F1F2P4.java where your given name begins with the characters N1N2 and your family name begins with the characters F1F2. For example my name is Ivor Page, so my source file will be called IVPAP4.java. 
Note that in all but the "java" extension, all characters are upper case.
4. Do not include your name anywhere in your project.
5. Your program's output must exactly match the format of the Expected Output above.
6. Do not use any Java Collection Classes except the Strings, arrays and ArrayLists.
7. You program must read from System.in and output to System.out.
8. Use good style and layout and comment your code well. 
9. Use the test files provided on the eLearning webpage for this class to test your program. 
10. Submit your ONE source code file to the eLearning Assignment Dropbox for this project. 
11. Don't submit a compressed file. Don't submit a .class file.

Reference no: EM13867840

Questions Cloud

Comprehensive marketing plan researching the same : Continue your comprehensive marketing plan researching the SAME company that you researched in previous units. Again, utilizing the CSU Online Library, you will research the various elements of the marketing plan as it relates to this company. In Uni..
How small lead collimator reduces off-focal radiation : Describe X-ray tube operation. Discuss principal components and explain how a small lead collimator reduces off-focal radiation.
Relation to the global economy and financial markets : relation to the global economy and financial markets.
Show the accounting equation effects : Schlitterbahn Waterslide Company issued 25,000, 10-year, 5 percent, $ 100 bonds on January 1 at face value. Interest is payable each December 31. Show the accounting equation effects and prepare journal entries for (a) The issuance of these bonds on ..
Use kruskal algorithm to construct a minimal spanning tree : 1. use Dijkstra's Single Source Shortest Path Algorithm to construct the shortest path from a given vertex S to all other vertices.2. use Kruskal's algorithm to construct a minimal spanning tree for the graph.
Analyze the policy development cycle : Create a 10- to 12-page policy proposal, utilizing a minimum of five scholarly sources in your research. Address the following in your proposal: State the social problem you wish to solve. Analyze the policy development cycle and the influence of s..
Compute shavers debt to asset ratio and time interest : Compute Shavers debt-to-assets ratio and times interest earned ratio. Based on these ratios, does it appear Shaver relies mainly on debt or equity to finance its assets? Is it prob-able that Shaver will be able to meet its future interest obligations..
What is the balls apparent speed : You are traveling 90 km/h and you throw a ball 47 km/h with respect to yourself. What is the balls apparent speed to a friend standing by the road when the ball is thrown straight ahead?
Discussion-financial management terminologies : Discussion-Financial Management Terminologies

Reviews

Write a Review

Computer Graphics Questions & Answers

  Find the normal to the triangle

Find the normal to the triangle. Assume that the triangle is given clockwise. Normalize the vector. Draw a figure showing that your normal is correct.

  What will the histogram of pixel intensities look like

Draw the cumulative histogram for this image (see Figure 1). What will the histogram of pixel intensities look like after applying histogram equalization?

  Create a quality product for a selected audience

Apply knowledge of poster design or website design to create a quality product for a selected audience - find the information resources you need for this project

  Create a gui message panel that uses 4 different fonts

Create a GUI message panel that uses 4 different fonts, colors and styles ( bold ect ) with messages of your choice.

  Rewrite programming to create a gui

Rewrite Programming Exercise to create a GUI. Your probram should let the user eanter the loan amound and loan period in the the number of years from the tests fields and it should sisplay the monthly and total payments for each interest rate start..

  Develop the image manipulations

Develop the image manipulations

  1 how could utv become an rs5 billion company by 2008 and

1. how could utv become an rs5 billion company by 2008 and an rs10 billion company by 2010? whatcould the role of the

  Specify a triangle with three mouse presses

Write a program that allows the user to specify a triangle with three mouse presses. After the first mouse press, draw a small dot. After the second mouse press, draw a line joining the first two points.

  Write a gui program with check buttons

Write a GUI program with check buttons that allow the user to select any or all of these services. When the user clicks a button the total charge should be displayed.

  How many minutes of uncompressed digital video can be stored

Approximately how many minutes of uncompressed digital video could be stored and played from a standard (single-speed) CD-ROM at 640 X 480 resolution using 256 colors?

  Dissertation proposal video presentation

This is your last research course for the DHA program. You have been working with the organization in which you will collaborate in completing your Action Research project.

  Read the article values-based service brands narratives

read the article values-based service brands narratives from ikea by edvardsson from the readings for this module.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd