Prims algorithm for minimum spanning tree, Programming Languages

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).



  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 containing your source code and all output files to the TA.


Posted Date: 2/19/2013 8:18:42 AM | Location : United States

Related Discussions:- Prims algorithm for minimum spanning tree, Assignment Help, Ask Question on Prims algorithm for minimum spanning tree, Get Answer, Expert's Help, Prims algorithm for minimum spanning tree Discussions

Write discussion on Prims algorithm for minimum spanning tree
Your posts are moderated
Related Questions
Assigment 01 Subject Code: ITE 2106 Subject Name: Software Engineering You run a software development organization catering to external clients to build software solutions. The bus

how to save bulk entries at a time using collections?

how to concatinate two strings in assembly

how do I get my actor to spin

I am trying to get right side triangle in visual logic using for loop

Extend the AirRaid game, so that the planes drop a bomb on the gun as they go over it. The gun has to move out of the way otherwise it will be destroyed if hit. Provide three lives

how to store an url in a dartabase(sql server 2005)? (or) create table b(url what is the datatype for url?

Write a program that will input two numbers from the keyboard and execute each of the signed and unsigned multiply and divide instructions.  For each instruction, the program shoul

I can attach or send the assignment instructions, but they''re rather long. 90% of the code is already written and given to us. The assignment is primarily rewriting and rearrangin

I have an assignment that requires from me to run multiple clients and one server ( Corba)