Problem: Prim's Algorithm
The problem we can solve using a priority queue is that of computing a minimum spanning tree. Given a fully connected undirected graph where each edge has a weight, we would like to find the set of edges with the least total sum of weights. Using the scenario:
You are an engineer and you are trying to figure out the best way to arrange for internet access in your Town. There are N (3 ≤ N ≤ 25) blocks in your town connected by M (N ≤ M ≤ 25) various streets and you can walk between any two streets in the town by traversing some sequence of roads.
However, you have got a limited budget and have determined that the cheapest way to arrange for internet access is to build some fiber-optic cables along existing roadways. You have a list of the costs of laying fiber-optic cable down along any particular street, and want to figure out how much money you will need to successfully complete the project, meaning that, at the end, every street will be connected along some sequence of fiber-optic cables.
As a computer scientist, you heard about Prim's algorithm in one of your programming classes. This algorithm is exactly the solution to your problem, but it requires a priority queue.
Write a program to create using a priority queue to implement a solution of Prim's algorithm.
Input data describing the graph will be arranged as a list of edges (streets and their fiber-optic cost) and for the program we will covert that to an adjacency list: for every node in the graph in the town, we will have a list of the nodes (streets) it's connected to and the weight (cost of building fiber-optic cable along).
adj[0] → (1, 1.0) (3, 3.0)
adj[1] → (0, 1.0) (2, 6.0) (3, 5.0) (4, 1.0) . . .
The response should include a reference list. Using one-inch margins, Times New Roman 12 pnt font, double-space and APA style of writing and citations.