Minimum spanning tree

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:

T(n)=O(V^2) [Adjacent matrix]--> ==Dense graph==

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 Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above.The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

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.

Translation: There is a problem with the head of the tropical island Laglia Mountain. A few years ago, a lot of foreign aid was spent on extra roads between villages. But the jungle constantly surpasses the roads, so the huge road network is too expensive to maintain. The Council of Senior Citizens must choose to stop maintaining some roads. The map on the upper left shows all the roads currently in use and the monthly cost of maintaining these roads. Of course, even if the route is not as short as before, some way must be adopted to maintain traffic between all villages. The dean of elders wanted to tell the council of elders how much money it would spend each month to maintain the road connecting all the villages. In the map above, these villages are marked A to I. The map on the right shows the cheapest roads that can be maintained, saving 216 acres per month. Your task is to write a program to solve such problems.

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