书海扬帆的博客

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

本篇文章仅供个人复习,因此以自己理解为首要目标,新人不懂勿喷,感谢。</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 <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define INT_MAX 1000000000 //开1<<30也可
int n,m,cnt,dis[100100],ans;
struct node{
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("%d\n",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 %d\n",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("%d\n",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 <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m,p[100100],ans;
struct node{
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("%d\n",ans);
return 0;
}

六、结语


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

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

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

Luogu题目地址(点我点我)

LOJ题目地址(点我点我)

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

“同学,这个学过吗?”
“学过啊!”

“来写一个我看看。”

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

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



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k