- +44 141 628 6080
- info@tutorsglobe.com

18,76,764

Questions

Asked

21,311

Experts

9,67,568

Questions

Answered

Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!

Submit Assignment
## Minimal Spanning Tree Problem, Prim’s Algorithm

Minimal Spanning Tree Problem

A tree can be defined as an acyclic, undirected and connected graph. A spanning tree is a subgraph of G, that is, undirected and connected graph, is a tree and consists of all the vertices of G. A minimum spanning tree is a spanning tree but has weights or lengths related with edges and the total weight is at the minimum.

Prim's Algorithm

Sample AssignmentAssume that it is desired to set up a cable communication network that connects major cities, which is revealed in the figure. Find out how the cities are linked such that the total cable mileage is reduced.

Answer

C = {LA} C' = {SE, DE, DA, EH, NY, DC}

C = {LA, SE} C' = {DE, DA, EH, NY, DC}

C = {LA, SE, DE} C' = {DA, EH, NY, DC}

C = {LA, SE, DE, DA} C' = {EH, NY, DC}

C = {LA, SE, DE, DA, EH} C' = {NY, DC}

C = {LA, SE, DE, DA, EH, NY} C' = {DC}

C = {LA, SE, DE, DA, EH, NY, DC} C' = { }

The resulting network is

Therefore the total cable mileage is 1100 + 1300 + 780 + 900 + 800 + 200 = 5080