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 wan
t 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)