联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> C/C++编程C/C++编程

日期:2020-06-07 07:06

Project 2

Assign 2020-5-14 (Thu)    Due 2020-6-8 (Mon)

Weight: 10% of the total course score.

Problem

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).


Determine the minimum amount Farmer John will have to pay to water all of his pastures.


Requirements:

You should first think about how to solve this problem with MST. Secondly, you should build an adjacency list representation of the graph, then use the Prim's Algorithm based on the priority queue to build MST, and give the answer according to the MST results.


Solution algorithm:

1.Build an adjacency list representation of the graph. (Please refer to page 7-9 of cs206 ch13 graph.pdf)

The adjacency list in the class slide is for a directed graph, but you can easily modify it for an undirected graph.

2. Create a heapNode for each vertex which will store key and other vertex information.

3. Create a priority queue. (Please refer to page 5-14 of CS206 CH8 PQ &Heap.pdf)

4. Prim-Jarnik Algorithm. (Please refer to page 17 of CS206 CH13 Graph.pdf)

5. Print the result.

The class material referred above contains headers and a large amount of C++ codes. You can use the codes, but sometimes you have to modify them and you have to check whether there are trivial bugs.

Submit:

1.Files to submit: CS206_studentID_name (CN).h  and CS206_studentID_name(CN).cpp.

2.The following classes definition is included in your header file. You should implement the classes and necessary methods in your .cpp file. Please refer to the course materials for details.


class ArrayBinaryTree {};

class BinaryHeapPQ {};

class Graph{

void  PrimMST (int Start); };

Note:

You can use the headers defined following the inheritance hierarchy: vector (growable array) <- array binary tree <- binary heap PQ. Binary heap PQ must be implemented, but its super classes can be used from STL.

3. Score

a)BinaryHeapPQ is well implemented. You should implement priority queue based on ArrayBinaryTree . (35%)

b)The class Graph except method PrimMST is well defined and implemented. (20%)

c)The method PrimMST (int Start) are well defined and implemented. (30%)

d)Correct representation of heapNode. (5%)

e)Output the solution correctly. (5%)

f)If there is memory leak, you will get 10% penalty.

g)Inclusion of important comments (documentation). (5%)


3.Submit by platform:

a)Submit through learning platform

b)File subject: CS206_studentID_studentName (CN).

c)Due date: 2020-6-8 (Mon).

d)No acceptance after 3 days.

e)15% penalty per day up to 3 days.

f)For no submission, the course grade will be lowered by one letter grade. For example, B0 -> C+

4.The following files can be used to test the code and then give answers to the above  problem.


The test data and code are below.

It means there are 10 pastures, W_1 to W_10 are


The values of the matrix are P_ij.

Farmer John may build a well in the fourth pasture and connect each pasture to it , the cost is  

3 + 2 +3+ 2 +3+ 3+3+4+3+2+2 = 27.


# include your header files

int main() {

   Graph_MST g6(11);

   g6.AddEdge(0, 1, 2); g6.AddEdge(0, 2, 2); g6.AddEdge(0, 3, 3); g6.AddEdge(0, 4, 4);

g6.AddEdge(0, 5, 6); g6.AddEdge(0, 6, 3);  g6.AddEdge(0, 7, 5);  g6.AddEdge(0, 8, 4);

g6.AddEdge(0, 9, 8);  

  g6.AddEdge(1, 0, 2); g6.AddEdge(2, 0, 2); g6.AddEdge(3, 0, 3); g6.AddEdge(4, 0, 4);

g6.AddEdge(5, 0, 6); g6.AddEdge(6, 0, 3);  g6.AddEdge(7, 0, 5);  g6.AddEdge(8, 0, 4);

g6.AddEdge(9, 0, 8);  


   g6.AddEdge(1, 2, 4); g6.AddEdge(1, 3, 3); g6.AddEdge(1, 4, 3);

g6.AddEdge(1, 5, 4); g6.AddEdge(1, 6, 6);  g6.AddEdge(1, 7, 5);  g6.AddEdge(1, 8, 5);

g6.AddEdge(1, 9, 5);


g6.AddEdge(2, 1, 4); g6.AddEdge(3, 1, 3); g6.AddEdge(4, 1, 3);

g6.AddEdge(5, 1, 4); g6.AddEdge(6, 1, 6);  g6.AddEdge(7, 1, 5);  g6.AddEdge(8, 1, 5);

g6.AddEdge(9, 1, 5);


   g6.AddEdge(2, 3, 2); g6.AddEdge(2, 4, 5);

g6.AddEdge(2, 5, 3); g6.AddEdge(2, 6, 4);  g6.AddEdge(2, 7,3);  g6.AddEdge(2, 8, 3);

g6.AddEdge(2, 9, 5);

g6.AddEdge(3, 2, 2); g6.AddEdge(4, 2, 5);  g6.AddEdge(5, 2, 3); g6.AddEdge(6, 2, 4);  g6.AddEdge(7, 2,3);  g6.AddEdge(8, 2, 3);

  g6.AddEdge(3, 4, 5);

g6.AddEdge(3, 5, 2); g6.AddEdge(3, 6, 5);  g6.AddEdge(3, 7,3);  g6.AddEdge(3, 8, 4);

g6.AddEdge(3, 9, 5);

 g6.AddEdge(4, 3, 5);

g6.AddEdge(5, 3, 2); g6.AddEdge(6, 3, 5);  g6.AddEdge(7, 3, 3);  g6.AddEdge(8, 3, 4);

g6.AddEdge(9, 3, 5);

g6.AddEdge(4, 5, 3); g6.AddEdge(4, 6, 8);  g6.AddEdge(4, 7,9);  g6.AddEdge(4, 8, 5);

g6.AddEdge(4, 9, 5);

g6.AddEdge(5, 4, 3); g6.AddEdge(6, 4, 8);  g6.AddEdge(7, 4,9);  g6.AddEdge(8, 4, 5);

g6.AddEdge(9, 4, 5);

g6.AddEdge(5, 6, 6);  g6.AddEdge(5, 7,5);  g6.AddEdge(5, 8, 3);

g6.AddEdge(5, 9, 4);

g6.AddEdge(6, 5, 6);  g6.AddEdge(7, 5,5);  g6.AddEdge(8, 5, 3);

g6.AddEdge(9, 5, 4);

g6.AddEdge(6, 7,5);  g6.AddEdge(6, 8, 6);

g6.AddEdge(6, 9, 9);

g6.AddEdge(7, 6,5);  g6.AddEdge(8, 6, 6);

g6.AddEdge(9, 6, 9);

   g6.AddEdge(7, 8, 4);  g6.AddEdge(7, 9, 6);

g6.AddEdge(8, 7, 4);  g6.AddEdge(9, 7, 6);

g6.AddEdge(8, 9, 4);   g6.AddEdge(9, 8, 4);

g6.AddEdge(10, 0, 5); g6.AddEdge(10, 1, 4); g6.AddEdge(10, 2, 4); g6.AddEdge(10, 3, 3);

g6.AddEdge(10, 4, 4); g6.AddEdge(10, 5, 5);  g6.AddEdge(10, 6, 3);  g6.AddEdge(10, 7, 3);

g6.AddEdge(10, 8, 4); g6.AddEdge(10, 9, 5);

g6.AddEdge(0, 10, 5); g6.AddEdge(1, 10, 4); g6.AddEdge(2, 10, 4); g6.AddEdge(3, 10, 3);

g6.AddEdge(4, 10, 4); g6.AddEdge(5, 10, 5);  g6.AddEdge(6, 10, 3);  g6.AddEdge(7, 10, 3);

g6.AddEdge(8, 10, 4); g6.AddEdge(9,10, 5);

std::cout << "MST found by Prim_MinQueue:\n";

   g6. PrimMST (2);


   system("pause");

   return 0;

}


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp