# Minimum spanning tree

This is the third day that I participated in the more text challenge. For details of the event, please check: more text challenge

### Problem introduction

Unblocked project

To transform the original roads between n cities into expressways, the original road network between these cities is shown on the right, and the number on each side represents the cost of expressway reconstruction (unit: 1 billion yuan) ). How to construct a highway network at the lowest cost so that any two cities are connected by highways?

### Algorithm overview

Minimum spanning tree

Minimal Spanning Trees (MST)

Any tree that consists of only the edges of the graph G and contains all the vertices of G is called the spanning tree of G

The weight of the spanning tree of the weighted undirected graph G is the sum of the weights of all the edges of the spanning tree

Minimum Spanning Tree is all right in the minimum spanning tree weight spanning tree

N vertices, edges selected N-1, construct a connected graph, and the heavy weights which minimize the sum of N-1 of edges

Analysis : Obviously, the minimum spanning tree is the solution to the problem we introduce. How to build a minimum spanning tree?

Now we introduce two algorithms for constructing minimum spanning tree, Prim algorithm and Kruskal algorithm.

### Prim

Prim's algorithm, in 1930 by the Czech mathematician Woyijiehe. Yar Nick was first discovered (Vojt ch Jarn k), in 1957 by the American computer scientist Robert .C . Primm (Robert C. Prim) independently discovered 1959, eminent Dutch computer scientist . Aizi Ge .W Dijkstra (Edsger W. Dijkstra) rediscovered the algorithm, also known as the Royal Nick algorithm or Primm - Royal Nick algorithm , With greedy selection properties --> Classic examples of greedy algorithm

Case Analysis:

Design ideas

(1) Choose a point s arbitrarily and set the set S={s}

(2) Choose a point j from **== not in the set S so that the distance between it and a point i in S is the shortest ==**, then (i, j) is an edge on the spanning tree, At the same time add point j to S

(3) Go to (2) and continue until all points have been added to the S set

**Summary: **Prim algorithm, with greedy points as the core, aims to put n points into the set s{}, which is suitable for dense graphs (fewer points and more edges)

That information about what data structure to record a vertex needs to be defined?

```int G[MAXN] [MAXN];
//Storage map, plastic is used here, it may be a bit more complicated in actual application, you need to customize the data type

int closeset[n], //Record the nearest neighbor of vertex i in S that is not in S closeset[i]

int lowcost[n], //Record the shortest distance from vertex i that is not in S to S, that is, the weight to the nearest neighbor

int   Used [n-]; //tag is accessed vertices, the vertex is visited labeled 1
copy the code```

initialization

```int n, m; //n stores the number of vertices, m stores the number of edges
int G[MAXN][MAXN];   //stores the graph

void  init () {
for ( int i = 0 ; i <n; i++){
for ( int j = 0 ; j <n; j++)
G[i][j] = INF;     //Initialize the distance between any two points in the graph to be infinite
}
}
Copy code```

Greedy choice

```void  prim () {
int closeset[n],//Record the nearest neighbors of vertices not in S in S
lowcost[n],//Record the shortest distance from vertices not in S to S, that is, to the nearest neighbor The weight
used[n];//Mark whether the vertex is visited, the visited vertex is marked as 1

for ( int i = 0 ; i <n; i++)
{
//Initialization, only the first point in S (0)
lowcost[i] = G[ 0 ][i];
//Get the distance from other vertices to the first point (0), not directly adjacent vertices For infinity

closeset[i] = 0 ;
//In the initial situation, the nearest neighbor of all points is the first point (0)

used[i] = 0 ;
//All points have not been visited in the initial situation
}
used[ 0 ] = 1 ;   //Access the first point (0) and add the first point to S

//Find a vertex closest to S in each loop
for ( int i = 1 ; i <n; i++)
{
int j = 0 ;
/*Calculate the distance from all unused vertices to the current S in each loop,
Get the shortest distance to S and the vertex number among unused vertices*/
for ( int k = 0 ; k <n; k++) //Core: Greed a point closest to s{} (find point)
if (( !used[k]) && (lowcost[k] <lowcost[j]))
j = k; //Because j is initially 0 (the first point of s), lowcost[0] is infinite
//If vertex k is not used and the distance to S is less than the distance from j to S, assign k to j

printf ( "%d %d %d\n" ,closeset[j] + 1 , j + 1 , lowcost[j]);
//Output the nearest neighbor to j in S, j, and the distance between them
used [j] = 1 ; //Increase j to S

/*Each loop is used to recalculate the distance from the vertex not in S to S after j is added to S,
Modify the distance from the edge adjacent to j to S, that is, update lowcost and closet */
for ( int k = 0 ; k <n; k++)
{
if ((!used[k]) && (G[j][k] <lowcost[k]))
//Relaxation operation, if k is not used, and the distance between k and j is smaller than the original distance between k and S
{
lowcost[k] = G[j][k];
//Use the distance between k and j as the new distance between k and S
closeset[k] = j;
//Set j as the nearest neighbor of k in S
}
}
}
}

Copy code```

Time complexity analysis:

Heap optimization (small root heap): T(n) = O(VlogV)+O(ElogV) = O(ElogV)

Heap optimization (Fibonacci heap): T(n) = O(E+VlogV)

Summary :

Prim's algorithm is an algorithm based on **== solving the minimum spanning tree == ** of weighted undirected graphs based on greedy thinking

The time complexity of Prim's algorithm is T(n)= O(V^2) , which is suitable for processing dense graphs ;

### Kurskal

==Join search + minimum spanning tree --> Kruskal algorithm==

Kruskal Algorithm

An algorithm for finding the minimum spanning tree

Published by Joseph Kruskal in 1956 [Joseph Bernard Kruskal, January 29, 1928-September 19, 2010, American mathematician, statistician, computer scientist, psychometric expert]

Design ideas

(1) Sort the edges according to their weights from small to large, and then judge them one by one. If the current edge is added, no ring will be generated , then the current edge is taken as an edge of the spanning tree

(2) A total of (V-1) edges are selected (V is the number of vertices), and the final result is the minimum spanning tree

Data structure: union search set

Data structure definition and initialization

```/* Define edge (x, y), weight is w */
struct  edge
{
int x, y;
int w;
};

edge e[MAX * MAX];
int rank[MAX]; /* rank[x] represents the rank of x*/
int father[MAX]; /* father[x] represents the parent node of x*/
int sum; /*stores the total weight of the minimum spanning tree */

/* Comparison function, sorted by weight in non-descending order*/
bool  cmp ( const edge a, const edge b)
{
return aw <bw;
}

Copy code```

And check set

```/* Initialize the set*/
void  make_set ( int x)
{
father[x] = x;
rank[x] = 0 ;
}

/* Find the set where the x element is located, and compress the path when backtracking*/
int  find_set ( int x)
{
if (x != father[x])
{
father[x] = find_set (father[x]);
}
return father[x];
}
/* Combine the set where x and y are located*/
int  union_set ( int x, int y, int w)
{
x = find_set (x);
y = find_set (y);
if (x == y) return  0 ; //
return 0 without merging if (rank[x]> rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
sum += w; //record weight
return  1 ; //combine returns 1, mark out whether the edge (x, y) can be added to the spanning tree
}

Copy code```

Time complexity analysis

Time required for edge sorting: T(n) = O(ElogE)

The implementation of Kruskal algorithm usually uses union search to quickly determine whether two vertices belong to the same set. **The worst case may be to enumerate all the edges. At this time, it needs to loop |E| times. **So the time complexity of this step is O(E (V)) [After using path compression, each query The time complexity used is the inverse function of the Ackerman function which grows very slowly - (x), which grows very slowly and can be regarded as a constant ]

T(n) = O(E (V)) + O(ElogE) = O(ElogE) --> sparse graph

### Example HDU-1301

Title description

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 <n <27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100.All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

The input consists of 1 to 100 data sets, followed by the last line containing only 0. Each data set starts with a row containing only the number n, where n is the number of villages, 1 <n <27, and the first n letters of the village alphabet are capitalized. Each data set is completed with n-1 lines, which start with alphabetical village labels. There is no phone in the last village. Each line of a village starts with a village label, followed by the number of roads from the village to the village with the letter label k. If k is greater than 0, the row continues with data for each of the k roads. The data for each road is the village label at the other end of the road, followed by the monthly maintenance cost of the road (in acms). The maintenance cost will be a positive integer less than 100. All data fields in this row are separated by a single space. The road network will always allow travel between all villages. The network will never exceed 75 roads. In the villages of other villages, no road will exceed 15 (before and after in the alphabet). In the example input below, the first dataset is displayed with the map above.

The output of each data set is an integer per line: the minimum monthly cost (in aacms) for maintaining the road system connecting all villages. Warning: The violent solution to check every possible road will not be completed in one minute.

enter

```9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
Copy code```

Output

```216
30
Copy code```

On the code , this is the Kruskal algorithm.

```# include  "bits/stdc++.h"
using  namespace std;
const  int maxx = 105 ;
int father[maxx];
int ran[maxx];
int ans = 0 ;
struct  node
{
int x, y;
int v;
} qq[ 30 ];
inline  bool  cmp (node  a, node b)
{
return av <bv;
}

inline  void  make_set ( int x)
{
father[x] = x;
ran[x] = 0 ;
}
inline  int  find ( int x)
{//Search for compressed path
if (father[x] == x)
{ //If your parent node is yourself, then the x node is the root node
return x;
}
return  find (father[x]); //return the root node of the parent node
}
inline  int  merge ( int x, int y, int v) //merge by rank
{
x = find (x);
y = find (y);
if (x == y)
return  0 ;
ans += v;
if (ran[x]> ran[y])
{
father[y] = x;
}
else
{
father[x] = y;
if (ran[x] == ran[y])
{
ran[y]++;
}
}
return  1 ;
}

int  main ()
{
int n, m;
while (cin >> n && n)
{
ans = 0 ;
m = 0 ;
for ( int i = 0 ; i <= n; i++)
{
make_set (i);
}
int x, y;
int v;
char a, b;

for ( int i = 0 ; i <n- 1 ; i++)
{
cin >> a >> x;
for ( int j = 0 ; j <x; j++)
{
cin >> b >> v;

qq[j + m].x = a-'A ' ;
qq[j + m].y = b-'A ' ;
qq[j + m].v = v;
/* code */
}
m += x;
}
sort (qq, qq + m, cmp);
int s = 0 ;
for ( int i = 0 ; i <m; i++)
{
if ( merge (qq[i].x, qq[i].y, qq[i].v))
{
s++;
}
if (s> n- 1 )
{
break ;
}
}
cout << ans << endl;
}
}
Copy code```