Implement a solution of prims algorithm

Assignment Help Computer Engineering

Reference no: EM132730960

Question: 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) .

Reference no: EM132730960

Questions Cloud

What is the implied value of each warrant : The bonds can be issued at par ($1,000 per bond). Assuming annual interest payments, what is the implied value of each warrant

Describe the plain view doctrine : Describe the plain view doctrine, and why it has such a significant impact on digital forensics? What are three approaches to determining whether the doctrine.

Effectiveness of any compensation system to attract : The effectiveness of any compensation system to attract, retain and align employee behavior and performance with the objectives

What are after-tax yields of the preferred stock and debt : A company's preferred stock has a pre-tax dividend yield of 7%, and its debt has a pre-tax yield of 8%. What are after-tax yields of the preferred stock

Implement a solution of prims algorithm : 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 edge

Define the five-step marketing research approach : Define the Five-Step Marketing Research Approach and discuss the importance of research in marketing.

Discuss the kind of organizational structure : Discuss the kind of organizational structure and design of your selected organization.

Evaluate the system engineering process : Evaluate the system engineering process from a design methods perspective and investigate Model-Based System Engineering (MBSE) used in your company.

Competitive strategies used by company main competitors : Describe the competitive strategies used by the company's main competitors. Which of these strategies are the most effective?

User Account

All Pages