首页 > > 详细

Algorithm作业代做、代写C++语言作业、代做c/c++编程设计作业、代写data作业 帮做Haskell程序|帮做C/C++编程

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;
}

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp2

联系我们 - QQ: 99515681 微信:codinghelp2
© 2014 www.7daixie.com
程序代写网!