Prims algorithm for minimum spanning tree, Programming Languages

Assignment Help:

Implement the Prim's algorithm with array data structure as described in slide 12 of the file 04mst.ppt. Your program should have a runtime complexity of O(n2) and should be as efficient as possible. It should be able to handle up to 6K nodes and 18M edges. Please use adjacency list to represent the graph.  You may use either C or C++ for the implementation.   

The input weighted undirected graph is specified in a text file in the format below:  

  <# of nodes>

  <# of edges>

 

  ...

   

For example, the following file describes a graph with 3 nodes (indexed 1, 2 and 3) and 2 edges ({1,2} with weigth 0.5 and {2,3} with weight 2.2).

   3

  2

  1 2 0.5

  2 3 2.2  

For the output, your program should display the total weight of the MST and write a file representing the MST in the same format as the input file above. 

Several graphs will be posted to test your program. Please make a table to report, for each graph posted, the number of nodes in the graph, the number of edges in the graph, the runtime, and the total weight of the MST. Please also report the processor model and clock frequency of the machine that you use to obtain the runtime. Please email a zip file named prog01-prim.zip containing your source code and all output files to the TA.

 


Related Discussions:- Prims algorithm for minimum spanning tree

Simple corba program, You are working in charge of a group of programmers a...

You are working in charge of a group of programmers at a software company. Your task is to assess and research CORBA and to produce a report to be given to the programmers detailin

Write script to clear the variables in the workspace, Write a script called...

Write a script called 'prob2.m' that asks the user if they wish to clear the variables in the workspace. If the user responds with the strings 'y' or 'yes' then the workspace shoul

Describe the hypermedia and hypertext, Question: (a) How does HTML all...

Question: (a) How does HTML allow you to: (i) turn an image into a clickable hyperlink? Include code to switch off the default border (ii) convert the above hyperlink i

Matlab fem, I need a program that writes the first column of the matrix. T...

I need a program that writes the first column of the matrix. The numbers in this column follow the pattern below: 1. Numbers start at 1 and count up to ''nels'' in increments of

Python: returning one dimensional list from strings , How to build one dime...

How to build one dimensional list from string and build string from a list? Suppose input string is: STACKOVERFLOW then the output list should be outputList = [S,T,A,C,K,O,V,E,R,F

Write use case description for the process, The following is the process an...

The following is the process an account holder of eBroker, a discount online brokerage firm, uses to sell stocks.  The user first logs in by entering the username and password.

Advance operating systems, Project2: A Simple Distributed Computing Platfor...

Project2: A Simple Distributed Computing Platform (Due at 11:59:59pm on 04/12/2012 (EST)) Description: You are asked to develop a replicator (client) that distributes a large job

C, Is it possible to get an assignment done within 2 hours

Is it possible to get an assignment done within 2 hours

program that uses a hash structure, Write a Perl program that uses a hash ...

Write a Perl program that uses a hash structure. The program should use a larger number of operations (100 or more) on this hash. To do that, use a random number generator to creat

Write Your Message!

Captcha
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