# Introduction to algorithm 11 -- minimum spanning tree grid length problem

1, Purpose
1. Be familiar with the basic idea of algorithm design
2. Master the idea of minimum spanning tree algorithm
2, Content and design idea

The State Grid Corporation of China wants to lay out an EHV transmission network across the country and connect all provincial capitals. In order to reduce costs and meet some hard requirements, the State Grid plans and layout according to the following five strategies.
(1) The length of the whole power grid is required to be the shortest.
(2) It is required to minimize the length of the whole power grid when a direct dedicated line is pulled between Xining and Zhengzhou
(3) It is required to minimize the length of the whole power grid not only between Xining and Zhengzhou, but also between Hangzhou and Changsha.
(4) Under the premise that Hong Kong and Macao, Macao and Guangzhou do not pull direct lines, the length of the whole power grid is the shortest.
(5) Shandong, Henan, Shaanxi, Gansu, Qinghai, Xinjiang and other provinces farther north are called northern provinces, and the rest are called southern provinces. If only one direct line is planned between the southern and northern provinces, how to minimize the length of the whole power grid.
Please calculate the optimal situation according to these five situations.
Tips:

1. If there is no special agreement, special lines can be pulled between cities, and the length is a straight line.
2. The distance calculation method between any two points on the earth can refer to the following documents: https://www.cnblogs.com/ycsfwhh/archive/2010/12/20/1911232.html
Excerpts are as follows:
The earth is A nearly standard ellipsoid with an equatorial radius of 6378.140 km, an polar radius of 6356.755 km and an average radius of 6371.004 km. If we assume that the earth is A perfect sphere, then its radius is the average radius of the earth, recorded as R. If the 0-degree longitude is used as the benchmark, the surface distance between any two points on the earth's surface can be calculated according to the longitude and latitude of the two points (the error caused by the earth's surface topography is ignored here, which is only A theoretical estimate). Let the longitude and latitude of the first point A be (LonA, LatA) and the longitude and latitude of the second point B be (LonB, LatB). According to the datum of the 0-degree longitude, the positive longitude (Longitude) is taken for the east longitude, the negative longitude (- Longitude) is taken for the west longitude, the 90 latitude (90 latitude) is taken for the north latitude, and the 90 + latitude (90+Latitude) is taken for the south latitude. Then the two points after the above processing are counted as (MLonA, MLatA) and (MLonB, MLatB). Then, according to the trigonometric derivation, the following formula for calculating the distance between two points can be obtained:

C = sin(MLatA)*sin(MLatB)*cos(MLonA-MLonB) + cos(MLatA)cos(MLatB)

Here, the units of R and Distance are the same. If 6371.004 km is used as the radius, Distance is the unit of kilometer. If other units, such as mile, are used, unit conversion needs to be done. 1 km = 0.621371192mile
If only the longitude is treated as positive and negative, and the latitude is not treated as 90 latitude (assuming that it is all in the northern hemisphere and only Australia in the southern hemisphere has application significance), the formula will be:

C = sin(LatA)*sin(LatB) + cos(LatA)*cos(LatB)cos(MLonA-MLonB)

The above can be deduced through simple triangular transformation.

1. The longitude and latitude of the national provincial capital cities are as follows.
```city,longitude,latitude
Shenyang,123.429092,41.796768
Changchun City,125.324501,43.886841
Harbin City,126.642464,45.756966
Beijing,116.405289,39.904987
Tianjin,117.190186,39.125595
Hohhot,111.751990,40.841490
Yinchuan City,106.232480,38.486440
Taiyuan City,112.549248,37.857014
Shijiazhuang City ,114.502464,38.045475
Jinan City,117.000923,36.675808
Zhengzhou City,113.665413,34.757977
Xi'an City,108.948021,34.263161
Wuhan,114.298569,30.584354
Nanjing City,118.76741,32.041546
Hefei,117.283043,31.861191
Shanghai,121.472641,31.231707
Changsha City,112.982277,28.19409
Nanchang City,115.892151,28.676493
Hangzhou,120.15358,30.287458
Fuzhou City,119.306236,26.075302
Guangzhou City,113.28064,23.125177
Taipei City,121.5200760,25.0307240
Haikou City,110.199890,20.044220
Nanning,108.320007,22.82402
Chongqing City,106.504959,29.533155
Kunming,102.71225,25.040609
Guiyang City,106.713478,26.578342
Chengdu,104.065735,30.659462
Lanzhou City,103.834170,36.061380
Xining City,101.777820,36.617290
Lhasa,91.11450,29.644150
Urumqi,87.616880,43.826630
Hong Kong,114.165460,22.275340
Macao,113.549130,22.198750
```

## 3, Use environment

C/C + + integrated compilation environment is recommended.

## 4, Experimental process

1. Write relevant experimental code

```#include<bits/stdc++.h>
using namespace std;

#define Infinity 65535
#define ERROR -1
#define Pi 3.14
#define R 6371.004

int Index;
string Arr={"Shenyang","Changchun","Harbin","Beijing","Tianjin","Hohhot","Yinchuan",
"Taiyuan","Shijiazhuang","Jinan","Zhengzhou","Xi'an","Wuhan","Nanjing","Hefei",
"Shanghai","Changsha","Nanchang","Hangzhou","Fuzhou","Guangzhou","Taipei","Haikou",
"Nanning","Chongqing","Kunming","Guiyang","Chengdu","Lanzhou","Xining","Lhasa",
"Urumqi","Hong Kong","Macao"};
double S={{123.429092,41.796768},
{125.324501,43.886841},
{126.642464,45.756966},
{116.405289,39.904987},
{117.190186,39.125595},
{111.751990,40.841490},
{106.232480,38.486440},
{112.549248,37.857014},
{114.502464,38.045475},
{117.000923,36.675808},
{113.665413,34.757977},
{108.948021,34.263161},
{114.298569,30.584354},
{118.76741,32.041546},
{117.283043,31.861191},
{121.472641,31.231707},
{112.982277,28.19409},
{115.892151,28.676493},
{120.15358,30.287458},
{119.306236,26.075302},
{113.28064,23.125177},
{121.5200760,25.0307240},
{110.199890,20.044220},
{108.320007,22.82402},
{106.504959,29.533155},
{102.71225,25.040609},
{106.713478,26.578342},
{104.065735,30.659462},
{103.834170,36.061380},
{101.777820,36.617290},
{91.11450,29.644150},
{87.616880,43.826630},
{114.165460,22.275340},
{113.549130,22.198750}};

typedef struct GNode
{
int Nv;
int Ne;
double G;
//	int Data;
} MGraph;

typedef struct ENode
{
int V1,V2;
double Weight;
} Edge;

MGraph* CreateGraph(int VertexNum)
{
int V,W;
MGraph* Graph;

Graph=new MGraph;
Graph->Nv=VertexNum;
Graph->Ne=0;

for (V=0;V<Graph->Nv;V++)
{
for (W=0;W<Graph->Nv;W++)
{
Graph->G[V][W]=Infinity;
}
}

return Graph;
}

void InsertEdge(MGraph* Graph,Edge* E)
{
Graph->G[E->V1][E->V2]=E->Weight;
}

MGraph* BuildGraph(MGraph* Graph,double D[])
{
Edge* E;
int V;
int Nv,Ne,i,j,k;
k=0;

Nv=34;
Ne=1156;

Graph=CreateGraph(Nv);
Graph->Ne=Ne;

for (V=0;V<Nv;V++)
{
Index[V]=V;
}

if (Graph->Ne!=0)
{
E=new Edge;

for (i=0;i<Nv;i++)
{
for (j=0;j<Nv;j++)
{
E->V1=Index[i];
E->V2=Index[j];
E->Weight=D[k];
InsertEdge(Graph,E);
k++;
}
}

}

return Graph;
}

int FindMin(MGraph* Graph,double dist[])
{
int MinV,V;
double MinDist=Infinity;

for (V=0;V<Graph->Nv;V++)
{
if (dist[V]!=0&&dist[V]<MinDist)
{
MinDist=dist[V];
MinV=V;
}
}

if (MinDist<Infinity)
{
return MinV;
}
else
{
return ERROR;
}
}

void Print(double a[],int b[],int c[],int k,MGraph* Graph)
{
int i,j,t;

for (i=0;i<k;i++)
{
cout<<Arr[b[i]]<<"--"<<Arr[c[i]]<<": "<<a[i]<<endl;
}
}

double Prim(MGraph* Graph,MGraph* MST)
{
int k=0;
double a;
int b,c;
double dist,TotalWeight;
int parent,V,W;
int VCount;
Edge* E;

for (V=0;V<Graph->Nv;V++)
{
dist[V]=Graph->G[V];
parent[V]=0;
}
TotalWeight=0;
VCount=0;

MST=CreateGraph(Graph->Nv);
E=new Edge;

dist=0;
VCount++;
parent=-1;

while(1)
{
V=FindMin(Graph,dist);
if (V==ERROR)
{
break;
}
E->V1=parent[V];
E->V2=V;
E->Weight=dist[V];
InsertEdge(MST,E);
TotalWeight+=dist[V];
dist[V]=0;
VCount++;

a[k]=E->Weight;
b[k]=E->V1;
c[k]=E->V2;
k++;

for (W=0;W<Graph->Nv;W++)
{
if (dist[W]!=0&&Graph->G[V][W]<Infinity)
{
if (Graph->G[V][W]<dist[W])
{
dist[W]=Graph->G[V][W];
parent[W]=V;
}
}
}
}

if (VCount<Graph->Nv)
{
TotalWeight=ERROR;
}

Print(a,b,c,k,Graph);

}

int main()
{
MGraph* Graph;
MGraph* MST;
double Total;
int i,j,k;
double D;
double C;

k=0;
for (i=0;i<34;i++)
{
for (j=0;j<34;j++)
{
C=sin(S[i]*Pi/180)*sin(S[j]*Pi/180)+cos(S[i]*Pi/180)*cos(S[j]*Pi/180)*cos(S[i]*Pi/180-S[j]*Pi/180);
D[k]=R*acos(C);
k++;
}
}

Graph=BuildGraph(Graph,D);
Total=Prim(Graph,MST);

cout<<Total;

return 0;
}

```

2. Write the idea of the algorithm.
(2) The second question is to draw a line between Xining and Zhengzhou, first connect the two cities, and then use the minimum spanning tree from Zhengzhou;
(3) On the basis of the second question, set a flag=0. When you encounter Hangzhou or Changsha, flag+1. When flag=1, skip the cycle, directly connect Hangzhou and Changsha, and then return to the cycle;
(4) On the basis of the first question, if the two end points are Hong Kong and Macao or Guangzhou and Macao, set its dist[V] to infinity, and then use the FindMin function, and the rest remain unchanged.
(5) Separate the north and south cities, use the Prim algorithm respectively, and then find the minimum value from the distance between the north and south cities. The combination of the three is the solution.
3. Output the grid data table of each group of experiments and the total length of the grid, and present it visually.

Keywords: C C++ Algorithm

Added by jeffwhite on Sat, 13 Nov 2021 01:10:23 +0200