Find Jobs
Hire Freelancers

C++ Prim's Algorithm Implementation

$30-250 USD

En curso
Publicado hace más de 9 años

$30-250 USD

Pagado a la entrega
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.
ID del proyecto: 6774670

Información sobre el proyecto

Proyecto remoto
Activo hace 9 años

¿Buscas ganar dinero?

Beneficios de presentar ofertas en Freelancer

Fija tu plazo y presupuesto
Cobra por tu trabajo
Describe tu propuesta
Es gratis registrarse y presentar ofertas en los trabajos

Sobre este cliente

Bandera de UNITED STATES
Chandler, United States
5,0
3
Forma de pago verificada
Miembro desde nov 24, 2014

Verificación del cliente

¡Gracias! Te hemos enviado un enlace para reclamar tu crédito gratuito.
Algo salió mal al enviar tu correo electrónico. Por favor, intenta de nuevo.
Usuarios registrados Total de empleos publicados
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
Cargando visualización previa
Permiso concedido para Geolocalización.
Tu sesión de acceso ha expirado y has sido desconectado. Por favor, inica sesión nuevamente.