首页 > itarticle > 图论入门-利用prim或kruskal算法求解最小生成树问题

图论入门-利用prim或kruskal算法求解最小生成树问题

admin 11月 10, 2020 0

学了半天，吭哧吭哧的，终于学到图论啦。。。

本篇文章仅供个人复习，因此以自己理解为首要目标，新人不懂勿喷，感谢。</blockquote>

一、引言

图论是组合数学中的一个分支，是组合数学中一颗璀璨的明珠。无论是在数学研究和计算机科学中都有着广泛的应用。图这个东西，说简单不简单，说难也确实不难。虽然有些知识可能有些晦涩，但只要理解透彻，搞清算法的详细意义，就能茅塞顿开。

二、图的基本概念

一般的算法书以及老师都会介绍。如果实在不懂，买本书，或者学会善用搜索引擎。

基本概念：无向图、有向图、完全图、连通图、稠密图、稀疏图、边权、权值、连通分量等

三、图的存储

对于图论知识的理解，一定是一个从具体到抽象的过程。如果真的理解不了，就把图画出来吧。

比如我们考察下面这个无向图（用什么软件画好呢？想了半天决定用OneNote）：

图有邻接矩阵和邻接表两种存储方法。
邻接矩阵就是考察每两点连线，然后运用二维数组存储这个连线的边权。比如上图中1号点到2号点连线的边权是10，则我们的二维数组a[1][2]=10. 以此类推。

邻接表的特点则是省空间，用链表存储节点之间的关系。

四、Prim算法求解最小生成树

核心：建立在邻接表的基础之上，然后……其实就是暴力啦

朴素实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define INT_MAX 1000000000 
int n,m,cnt,dis[100100],ans;
struct {
  int d;
  int v;
  node next;
  //链表 
}pool[400000],e[100010]; //内存池 
void addedge(int u,int v,int d){
   node p=&pool[++cnt],q=&pool[++cnt]; //p: dis(u,v) q:dis(v,u)
  p->v=v,p->d=d,p->next=e[u],e[u]=p; //第一个d是结构体中的d，第二个是形参 
   q->v=u,q->d=d,q->next=e[v],e[v]=q; 
}

int main(){
    scanf("%d%d",&n,&m);
   int u,v,d;
  for(int i=1;i<=m;i++){
      scanf("%d%d%d",&u,&v,&d);
      addedge(u,v,d);
  }
    dis[1]=0;
    for(int i=2;i<=n;i++) dis[i]=INT_MAX;
   int k=1,min_d,min_p; //md表示最小距离 mp表示最小的点的编号 
   for(int i=1;i<n;i++){
       for(node *p=e[k];p;p=p->next) //找链 p;表示p!=NULL 
         if(dis[p->v] > p->d) dis[p->v]=p->d;
     //找最小值
      min_d=INT_MAX;
       for(int j=1;j<=n;j++)
           if(dis[j] && dis[j]<min_d)
               min_d=dis[j],min_p=j;
        ans+=dis[min_p];
     dis[k=min_p]=0;
  }  
  printf("%dn",ans);
 return 0;
   }

优化：

在找最小值的时候，能不能再降一些复杂度呢？由此我们想到了堆结构（跟线段树非常非常相似）。下面是优化后的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <climits> 
using namespace std;
typedef long long ll;
ll n,m,cnt,dis[500500],ans,flag[500500]; //flag[i]=1表示已经找过了 =0表示尚未找过 
struct node{
  ll d;
    ll v;
    node *next;
  //链表 
}pool[500500],*e[500500]; //内存池 
void addedge(ll u,ll v,ll d){
 node *p=&pool[++cnt],*q=&pool[++cnt]; //p: dis(u,v) q:dis(v,u)
   p->v=v,p->d=d,p->next=e[u],e[u]=p; //第一个d是结构体中的d，第二个是形参 
    q->v=u,q->d=d,q->next=e[v],e[v]=q; 
}
struct heap{
  ll d,p;
}h[500500];
ll L=1;
void change(ll i,ll d){ //第i个点的值修改为d 
  h[i+L-1].d=d;
    for(ll j=(i+L-1)/2;j;j/=2)
       if(h[2*j].d<h[2*j+1].d) h[j]=h[2*j];
      else h[j]=h[2*j+1]; 
}
int main(){
   scanf("%d%d",&n,&m);
 ll u,v,d;
    for(ll i=1;i<=m;i++){
     scanf("%d%d%d",&u,&v,&d);
        addedge(u,v,d);
  }
    dis[1]=0;
    for(ll i=2;i<=n;i++) dis[i]=ll_MAX;
   //建立堆结构 
 while(L<n) L*=2;
  for(ll i=L;i<=L+n-1;i++) h[i].d=dis[i-L+1],h[i].p=i-L+1;
  for(ll i=L+n;i<2*L;i++) h[i].d=ll_MAX;
    for(ll i=L-1;i>0;i--){
        if(h[2*i].d<h[2*i+1].d) h[i]=h[2*i];
      else h[i]=h[2*i+1]; 
     //结构体中的每一个元素都赋值 
 }
    //printf("%d %dn",h[1].p,h[1].d);
    ll k;
    for(ll i=1;i<=n;i++){
     k=h[1].p; //k=最小值的编号
     ans+=dis[k];
     flag[k]=1;
       //下面改结构体 
        change(k,ll_MAX);
        for(node *p=e[k];p;p=p->next)
         if(flag[p->v]==0 && dis[p->v]>p->d){
             dis[p->v]=p->d;
                change(p->v,p->d); 
            } 
   }
    printf("%dn",ans);
   return 0;
    }

五、Kruskal算法求解最小生成树

核心：在邻接表的基础之上，跑并查集。

下面看一下代码实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m,p[100100],ans;
struct {
 int u,v,d;
}e[300100];
int find(int i){
  if(p[i]==0) return i;
  else return p[i]=find(p[i]);
}
void Union(int i,int j){
    p[i]=j;
}
bool cmp(node x,node y){
 return x.d<y.d; 
}
int main(){
 scanf("%d%d",&n,&m);
   for(int i=1;i<=m;i++)
       scanf("%d%d%d",&e[i].v,&e[i].u,&e[i].d);
   for(int i=1;i<=m;i++)
       if(find(e[i].u)!=find(e[i].v)){
         ans+=e[i].d;
         Union(find(e[i].u) , find(e[i].v));
      } 
   printf("%dn",ans);
 return 0;
   }

六、结语

由于最小生成树是一类题目，因此AC掉模板题至关重要。

Luogu的数据好像很水的样子，暴力都可以轻松过掉。

不过LOJ好像就不行了，Luogu AC代码交上去只得10分。

Luogu题目地址（点我点我）

LOJ题目地址（点我点我）

总之就是学习完新知识后要及时复习总结，上课讲的理论下课后一定要手动实现，重要的部分尤其是解题思路、算法复杂度和证明方法一定要记下来。这样可以避免出现遗忘现象。

“同学，这个学过吗？”
“学过啊！”

“来写一个我看看。”

“我……我不会啊！怎么写来着。。。”

要上考场了还像上面这样，就彻底凉了。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能