In this assignment you will create a C++ program (main.cpp) that implements both Kruskals Algorithm (pg. 704 of the textbook) and Prims Algorithm (pg. 707 of the textbook) to find a minimum spanning tree for a simple, undirected, weighted graph. The input to the program will be a weighted adjacency matrix, which is described below. The output from the program will be the weighted adjacency matrix for the minimum spanning tree produced by Prims Algorithm.

Prim's Algorithm from textbook:

Input: G [a connected weighted graph with n vertices where n is a positive integer]

Algorithm Body:

[Build a subgraph T of G by starting with any vertex v of G and attaching edges (with their endpoints) one by one to an as-yet-unconnected vertex of G, each time choosing an edge of least weight that is adjacent to a vertex of T .]

1. Pick a vertex v of G and let T be the graph with one vertex, v, and no edges.

2. Let V be the set of all vertices of G except v.

3. for i := 1 to n 1

3a. Find an edge e of G such that (1) e connects T to one of the vertices in V, and (2) e has the least weight of all edges connecting T to a vertex in V. Let w be the endpoint of e that is in V.

3b. Add e and w to the edge and vertex sets of T , and delete w from V.

next i

Output: T [T is a minimum spanning tree for G.]