There are two best known algorithms for minimum spanning trees. One isPrimAlgorithms, the other one is of courseKruskalAlgorithms, next, I will do my best to introduce these two algorithms, but also a review of their own learning

As usual,Template problem portal

First, the one I like better, and the one that’s relatively easy to codeKruskalalgorithm

By the definition of discrete mathematics

> < p style = "max-width: 100%; clear: both; min-height: 1px; < p style = "max-width: 100%; box-sizing: inherit! Important;Copy the code

Therefore, we can refine the process of the algorithm as follows

1. Determine whether the edge can be inserted and perform the following operations: 1. Inc (ANS, path length) 2. Merged connected branchCopy the code

1. For sorting, library functions are availablesort

2. For the step of judging whether the edge can be inserted, our idea is to look up the set by means of combination. If the two ancestors of this edge are the same, then the insertion of this edge will obviously constitute a ring, so it is skipped

3. The end of the algorithm is marked by the number of added edgesn - 1

Now that the algorithm has been introduced, let’s think about the memory edgeThe data structure, we select the struct array shown below

struct Edge { int u; // start int v; // end int w; } e[100010];Copy the code

For parallel search set processing is simply mentioned

1. Initialization

void init() {
    for(int i = 1; i <= n; i++) { fa[i] = i; }}Copy the code

2. Search for ancestral functions,Path compression algorithm

int find (int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
Copy the code

3. Merge operation, which merges two vertices belonging to different sets into the same set

void union_(int x, int y) {
    int fx = find(x);
    int fy = find(y);

    fa[fx] = fy;
}
Copy the code

It doesn’t feel like much, so just post the whole AC code

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100 + 10;
int n, cnt, fa[MAXN], sum, ans;

void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find (int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

void union_(int x, int y) {
    int fx = find(x);
    int fy = find(y);

    fa[fx] = fy;
}

struct Edge {
    int u;
    int v;
    int w;
} e[100010];


bool cmp (Edge a, Edge b) {
    returna.w < b.w; } // This problem should take and look up the set to determine if it will form a ring, and then use an array of structs to store the edge information intmain() {
    cin >> n;

    init();

    int h;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> h;
            if(j > I) {// if (j > I) { e[cnt].v = j; e[cnt].w = h; } } } sort(e + 1, e + 1 + cnt, cmp);for (int i = 1; i <= cnt; i++) {
        int u = e[i].u;
        int v = e[i].v;
        if(find(u) ! = find(v)) { union_(u, v); sum++; ans += e[i].w;if (sum == n - 1) {
                break;
            }
        }
    }

    cout << ans;
    return 0;
}
Copy the code

twoPrimealgorithm

PrimThe algorithm is also a greedy algorithm, which is equal toKruskalThe difference between algorithms is thatPrimThe algorithm is to start from one point at a time and select the smallest edge of the current point that does not form the ring, andKruskalThe algorithm is choosing the smallest edge that doesn’t form a ring from the global point of view, soPrimThe algorithm is relatively complicated

Obviously, it is time consuming to select the best edge from the current vertex each time, so we can heap optimise this stepPriority queue)

The data structure of this algorithm is a little bit more complicated, and I’m going to introduce it

bool vis[MAXN]; Struct Edge {int u; // start int v; // end int w; Bool operator <(const struct Edge& n) const {returnw > n.w; } // Overload the comparison operator for the following priority queue}; vector <Edge> g[MAXN]; Priority_queue <Edge> Edge; // Priority queues are not explainedCopy the code

1. Read data

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        int w;
        cin >> w;
        if (w == 0) continue; g[i].push_back(Edge{i, j, w}); }}Copy the code

2. Add adjacent edges to the team starting from 1

vis[1] = true;
for (int i = 0; i < g[1].size(); i++) {
    edge.push(g[1][i]);
}
Copy the code

3. PerformPrimAlgorithm, until the number of edges is zeron - 1So far,

 while (cnt < n - 1){
    int w = edge.top().w;
    int v = edge.top().v;
    edge.pop();
    
    if(vis[v]) {// Already accessedcontinue;
    }

    vis[v] = true; ans += w; //ans is the result cnt++; // CNT is the edge counterfor (int i = 0; i < g[v].size(); i++) {
        if(! vis[g[v][i].v]) { edge.push(g[v][i]); }}}Copy the code

The complete code will not be posted

Well, that’s it for today