Purpose : Practice Kruskal algorithm and Quicksort

Situation description: Chipmunk Thanksgiving

As the Chipmunk Club prepares to get into the festive spirit for Thanksgiving, they plan to sprinkle candy on the paths between eight chipmunk homes. However, the mutual aid association has a limited budget, so a minimum spanning tree is needed to connect these homes at minimal cost. In this tree, each edge represents a path for spreading candy, and the weight represents the total cost of spreading candy. Please help design a minimum spanning tree to ensure maximum cost savings while creating a festive atmosphere.

Project Content:

(1) Representation of graph

Chipmunk Aid has compiled a map of all chipmunk homes, as shown below:

Please store this map in adjacency matrix to facilitate subsequent algorithm operation. If there is no path between two nodes, please indicate it with 'X'.

The following is a simple output example of three nodes A, B, and C being used as part of the map:

For the project output, please output the 9*9 matrix completely (the first column and the first row are the node names, and the 8*8 number matrix)

(2) Quicksort:

When using Kruskal to build a minimum spanning tree, the ascending sorting algorithm needs to be used. In order to consider the fastest average time, the sorting algorithm in Kruskal in the job is Quicksort based on the (in-place) Hoare partition scheme, and specifies that the rightmost element is used as the pivot, and the left subarray is processed first, and the right subarray is processed later. Among them, if there is a value equal to pivot, it will not be exchanged.

After each pivot exchange in Quicksort, please print "step k:", followed by the order of the current sides to check for correctness. k = 0 represents not yet exchanged, k = 1 represents the result of the first exchange, and so on.

Here are the first 5 lines of correct output:

Explanation of the meaning of step 0 and step 1 in the picture: at step 0, (l, 4) will be selected as the pivot, then (j, 2) will be the big element, (a, 7) will be the small element, so (j, 7) will be ,2) Exchange with (a,7), then, the small element and the big element will go to (d,7) and (c,1) respectively, but because the index of the small element > the index of the big element, it is not done Any action, finally exchange (l,4) with the big element to obtain the result of step 1.

Please note that each edge is presented as: (edge code, weight). For example, there is an edge with a weight of 7 between nodes A and B in the map, expressed as (a, 7).

(3) Minimum spanning tree

Use the edges sorted in the previous question to build a minimum spanning tree using the Kruskal algorithm, and print out the process of selecting edges. If you want to avoid a cycle and not select an edge, you should also indicate which edge is ignored to fully understand the problem. Explain the steps of the algorithm. Each time an edge is selected, the information of this edge will be output. In addition, please follow the output format in the figure below, which is part of the output of the correct answer:

Please note that the output stops when you determine that the minimum spanning tree has 7 edges.

Requirements:

(1) Quicksort must have an independent function to identify program blocks.

(2) The output of the edge must be presented in the format defined in the first sub-question of the second question.

(3) The output between different questions must be separated by a dividing line composed of '-'.

(4) Please write this assignment in C++.

I've got this code below for number (1)Representation of Graph, which is the matrix, i don't know if it's correct or not, but please help me continue with number (2)Quicksort and (3)Minimum Spanning tree

#include #include #include

using namespace std;

// Structure to represent an edge struct Edge { char from, to; int weight; Edge(char u, char v, int w) : from(u), to(v), weight(w) {} };

class GraphMST { private: int numVertex; std::vector<:vector>> adjMatrix;

public: GraphMST() : numVertex(0) {}; GraphMST(int n) : numVertex(n) { adjMatrix.resize(numVertex); for (int i = 0; i

void GraphMST::AddEdge(char from, char to, int weight) { int i = from - 'A'; int j = to - 'A'; adjMatrix[i][j] = weight; }

// Function to print the adjacency matrix void GraphMST::printAdjacencyMatrix() { cout

for (int i = 0; i

int main() { GraphMST g8(8); g8.AddEdge('A', 'B', 7); g8.AddEdge('A', 'C', 3); g8.AddEdge('A', 'D', 1); g8.AddEdge('B', 'A', 7); g8.AddEdge('B', 'F', 7); g8.AddEdge('C', 'A', 3); g8.AddEdge('C', 'E', 7); g8.AddEdge('D', 'A', 1); g8.AddEdge('D', 'E', 6); g8.AddEdge('D', 'G', 7); g8.AddEdge('E', 'C', 7); g8.AddEdge('E', 'D', 6); g8.AddEdge('E', 'F', 6); g8.AddEdge('E', 'G', 5); g8.AddEdge('E', 'H', 2); g8.AddEdge('F', 'B', 7); g8.AddEdge('F', 'E', 6); g8.AddEdge('F', 'H', 5); g8.AddEdge('G', 'D', 7); g8.AddEdge('G', 'E', 5); g8.AddEdge('H', 'E', 3); g8.AddEdge('H', 'F', 5); g8.AddEdge('H', 'G', 4);

g8.printAdjacencyMatrix();

return 0; }

ABAX73B7XC3X step:(a,7)(b,3)(c,1)(d,7)(e,7)(f,6)(g,7)(h,6)(i,5)(j,2)(k,5)(1,4)step1:(j,2)(b,3)(c,1)(1,4)(e,7)(f,6)(g,7)(h,6)(i,5)(a,7)(k,5)(d,7)step2:(c,1)(b,3)(j,2)(1,4)(e,7)(f,6)(g,7)(h,6)(i,5)(a,7)(k,5)(d,7)step3:(c,1)(j,2)(b,3)(1,4)(e,7)(f,6)(g,7)(h,6)(i,5)(a,7)(k,5)(d,7)step4:(c,1)(j,2)(b,3)(1,4)(e,7)(f,6)(g,7)(h,6)(i,5)(a,7)(k,5)(d,7) (c,1)(j,2)(b,3)(1,4)(k,5)(i,5)isignored