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

   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.

 

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
Language-Integrated Query Language integrated query (LINQ, obvious "link") is a Enthusiasm .NET Structure element that contributes ancient data querying abilities to .NET dialects,

Windows XP using C# load a binary file and send it thru a USB port to the USB port of STM32. STM32 received the file and then write it into an I2C EEPROM.

Produce a hierarchy chart, a structured flowchart, and a Pascal program (with appropriate comments) to generate the Sales Commission Report shown below. The commission for each sal

Complete the following program to move a value of 0xFFH to PORTB LIST p=18f4550 #include org 0x0000 movlw 0x00 _________ movlw 0xFF movwf PORTB end .

Write a program that can facilitate searching by indexing text files according to words. In this task, you are given a large text file, sample.txt, which you will need to index the

In combat simulation software, exploding land mines cause damage to military vehicles. In addition to the damage done to the vehicles themselves, we are interested in the number of

In this activity, you are going to place components on a sheet and connect them with virtual wires to create a simple digital circuit. You will simulate the circuit to verify the c

Each of the following two procedures defines a method for adding two positive integers in  terms of the procedures inc, which increments its argument by 1, and dec, which decrement

about how to create the program in c

a) Write a program i_language(Sentence,NewSentence) that translates a sentence to the i-language. In this language all vowels are changed to i and all other characters are kep