Use Prim and Kruskal algorithms to solve the minimum spanning tree

Hits: 0

This paper gives Prim and Kruskal two solutions to solve [the minimum spanning tree] solving process and code through specific algorithm template questions~

From simple to deep, easy to understand

The topic is selected from [Luogu P3366]

Topic description

For example, given an undirected graph, find the minimum spanning tree, and output if the graph is not connected  orz.

input format

The first line contains two integers N,M, indicating that the graph has N nodes and M undirected edges.

The next M lines each contain three integers Xi​,Yi​,Zi​, indicating that there is an undirected edge of length Zi​ connecting nodes Xi​, Yi​.

output format

If the graph is connected, output an integer representing the sum of the lengths of the edges of the minimum spanning tree. Output if the graph is not connected  orz.

Input and output example

Enter 1

</p> <h1>include<cstdio></h1> <h1>include<queue></h1> <h1>include<cstring></h1> <h1>include<algorithm></h1> <h1>define R register int</h1> <p>using namespace std;</p> <p>int k,n,m,cnt,sum,ai,bi,ci,head[ 5005 ],dis[ 5005 ],display[ 5005 ];</p> <p>struct Edge { int v,w,next; }e[400005];</p> <p>void add(int u,int v,int w) { e[++k].v=v; e[k].w=w; e[k].next=head[u]; head[u]=k; }</p> <p>typedef pair <int,int> pii; priority_queue <pii,vector\<pii>,greater\<pii> > q;</p> <p>void prim() { dis[1]=0; q.push(make_pair(0,1)); while(!q.empty()&&cnt<n) { int d=q.top().first,u=q.top().second; q.pop(); if(vis[u]) continue; cnt++; sum+=d; vis[u]=1; for(R i=head[u];i!=-1;i=e[i].next) if(e[i].w<dis[e[i].v]) dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v)); } }</p> <p>int main() { memset(dis,127,sizeof(dis)); memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(R i=1;i<=m;i++) { scanf("%d%d%d",&ai,&bi,&ci); add(ai,bi,ci); add(bi,ai,ci); } prim(); if (cnt==n)printf("%d",sum); else printf("orz"); }

output 1

</p> <h1>include<iostream></h1> <h1>include<stdio.h></h1> <h1>include<math.h></h1> <h1>include<algorithm></h1> <p>using namespace std;</p> <h1>define MAX_N 5000+5</h1> <h1>define MAX_M 200000+5</h1> <p>struct edge{ int u,v; int w; }E[MAX_M]; int f[MAX_N]; int n,m; bool cmp(edge a,edge b){ return a.w < b.w; } void init(){ for(int i=1;i<=n;i++) f[i] = i; } int find(int x){ if(f[x] == x) return x; return f[x] = find(f[x]); } void merge(int x,int y){ f[find(x)] = find(y); } int Kruskal(){ int ans = 0, cnt = 0; init(); sort(E+1,E+1+m,cmp); for(int i = 1;i<=m;i++){ if(cnt == n-1) break; if(find(E[i].u) != find(E[i].v)){ merge(E[i].u,E[i].v); ans += E[i].w; cnt++; } } if(cnt != n-1) return 0; return ans; } int main(){ scanf("%d%d",&n,&m); for(int i = 1;i<=m;i++) scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w); int ans = Kruskal(); if(ans) printf("%d",ans); else printf("orz"); return 0; }

Instructions/Tips

Data size:

For 20% of the data, N≤5, M≤20.

For 40% of the data, N≤50, M≤2500.

For 70% of the data, N≤500, M≤104.

For 100% data: 1≤N≤5000, 1≤M≤2×10^5, 1≤Zi​≤10^4.

foreword

The difference between the two: Prim is better than Kruskal in dense graphs and worse than Kruskal in sparse graphs. Prim is to find the minimum value of the connected edges of the updated nodes, and Kruskal is to sort the edges directly.

Both are actually greedy ideas.

Prim algorithm idea:

Prim’s idea is to use any node as the root, then find all the edges adjacent to it (just use a loop), then update the new node and use this node as the root to continue the search, and maintain an array: dis, which acts as The shortest distance from a used point to an unused point.

The specific algorithm flow chart is as follows:

optimization:

but! Since the data of this question is relatively large, we should do some optimization

For example, Prim can use priority queues (aka heaps) to optimize algorithms

Kruskal algorithm idea:

The idea of ​​Kruskal algorithm is easier to understand than Prin. First sort the edges according to their weights, select edges with smaller weights first with a greedy idea, and connect them in turn. If there is a loop, skip this edge and continue to search until the number of edges that have been used is one less than the total number of points. Can.

The specific algorithm flow chart is as follows:

optimization:

but! Since the data of this question is relatively large, we should do some optimization

For example, Kruskal can use union lookup to optimize it

Prim problem solving code:

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define R register int
using namespace std;

int k,n,m,cnt,sum,ai,bi,ci,head[ 5005 ],dis[ 5005 ],display[ 5005 ];

struct Edge
{
    int v,w,next;
}e[400005];

void add(int u,int v,int w)
{
    e[++k].v=v;
    e[k].w=w;
    e[k].next=head[u];
    head[u]=k;
}

typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;

void prim()
{
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n)
    {
        int d=q.top().first,u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        cnt++;
        sum+=d;
        vis[u]=1;
        for(R i=head[u];i!=-1;i=e[i].next)
            if(e[i].w<dis[e[i].v])
                dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));
    }
}

int main()
{
    memset(dis,127,sizeof(dis));
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(R i=1;i<=m;i++)
    {
        scanf("%d%d%d",&ai,&bi,&ci);
        add(ai,bi,ci);
        add(bi,ai,ci);
    }
    prim();
    if (cnt==n)printf("%d",sum);
    else printf("orz");
}

Kruskal’s problem-solving code:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define MAX_N 5000+5
#define MAX_M 200000+5
struct edge{
    int u,v;
    int w;
}E[MAX_M];
int f[MAX_N];
int n,m;
bool cmp(edge a,edge b){
    return a.w < b.w;
}
void init(){
    for(int i=1;i<=n;i++) f[i] = i;
}
int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge(int x,int y){
    f[find(x)] = find(y);
}
int Kruskal(){
    int ans = 0, cnt = 0;
    init();
    sort(E+1,E+1+m,cmp);
    for(int i = 1;i<=m;i++){
        if(cnt == n-1) break;
        if(find(E[i].u) != find(E[i].v)){
            merge(E[i].u,E[i].v);
            ans += E[i].w;
            cnt++;
        }
    }
    if(cnt != n-1) return 0;
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=m;i++)
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
    int ans = Kruskal();
    if(ans) printf("%d",ans);
    else printf("orz");
    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.