Em Andamento

C++ Prim's Algorithm Implementation

In this assignment, you will be implementing the Prim's algorithm to find a minimum spanning tree and its total weight. It should also compute π value for each node and key value for each node (show π and key array content.). You will also need to implement a Heap data structure.

The example input graph is the following:

9

Helium Fluorine/5 Calcium/6

Aluminum Dysprosium/21

Calcium Fluorine/2 Dysprosium/12 Helium/6

Iodine Barium/24 Europium/14

Dysprosium Calcium/12 Aluminum/21 Europium/28

Europium Dysprosium/28 Fluorine/29 Iodine/14

Fluorine Calcium/2 Helium/5 Europium/29

Gallium Barium/17

Barium Iodine/24 Gallium/17

where the first number is the number of nodes/vertices followed by a blank line, then each line after that is a vertex name followed by other vertices reachable with a cost; line 3 indicates from Helium there is an edge to Fluorine (weight 5), and to Calcium (weight 6).

Note: all edges are directed and that edges may appear more than once: Aluminum to Dysprosium, Dysprosium to Aluminum. You might see a line with a vertex name without any other vertices following. That means that there is no edge coming from the vertex.

Input will end with a blank line (after node and edge information, a user hits return)

1. Using the given input, store this information as an adjacency list or an adjacency matrix. You should store them in alphabetical order.

2. Define a priority queue using a heap. A heap will be an array and its size will be same as the number of nodes in the graph. You will also need to define functions, build-heap(), decrease-key(), and extract-min(). You can add additional functions if necessary, but points are allocated to define these three functions.

3. Create arrays π and key.

4. Using the same data set, calculate a minimum spanning tree using Prim's algorithm by creating MST-Prim function

and print the minimum spanning tree as follows, and also display the total tree weight, the final π array content, and final key array content:

The minimum spanning tree produced by the Prim's algorithm consists of the following edges:

Aluminum -> Dysprosium with key 21

Dysprosium -> Calcium with key 12

Calcium -> Fluorine with key 2

Fluorine -> Helium with key 5

Dysprosium -> Europium with key 28

Europium -> Iodine with key 14

Iodine -> Barium with key 24

Barium -> Gallium with key 17

The total tree weight is 123

The array pi content:

pi[Aluminum]= none

pi[Barium]= Iodine

pi[Calcium]= Dysprosium

pi[Dysprosium]= Aluminum

pi[Europium]= Dysprosium

pi[Fluorine]= Calcium

pi[Gallium]= Barium

pi[Helium]= Fluorine

pi[Iodine]= Europium

The array key content:

key[Aluminum]=0

key[Barium]=24

key[Calcium]=12

key[Dysprosium]=21

key[Europium]=28

key[Fluorine]=2

key[Gallium]=17

key[Helium]=5

key[Iodine]=14

Print all vertex pairs (edges) with their weight in the order that they were added to the tree, and the total tree weight.

Habilidades: Programação C++

Ver mais: vertices nodes, tree structure programming, tree structure in c, tree structure algorithm, tree of data structure, tree of a graph, tree in data structure using c, tree in data structure and algorithm, tree in data structure, tree in algorithm, tree graph, tree data structure in c, tree data structure implementation in c, tree data structure example, tree data structure c, tree and graph in data structure, tree and graph data structure, tree and graph, structure graph, set of pairs, set data structure, set algorithm, queue in data structure with example, queue in data structure, queue implementation in data structure

Acerca do Empregador:
( 3 comentários ) Chandler, United States

ID do Projeto: #6774670

Premiar a:

iWillSolutions

A proposal has not yet been provided

$100 USD em 7 dias
(4 Avaliações)
2.7