一本通提高篇学习笔记-图论基础

最短路和最小生成树的话这得是第三次整理了,强连通分量应该也是第二次,拓扑排序虽然以前没有过知识点整理但是做过题,总之是一点很基础的东西。

*干货量巨大警告


图的基本概念

图是一种多对多的数据结构,通俗的来讲,有一些点,点和点之间由各种边相连,就是一个图。精准的定义:图是一种这样的数据结构,假如把图记作G,则有G = (V,E),V是图上的点构成的集合,E是点与点之间的关系构成的集合,即边集合。可以看出,图其实是由两个集合构成的数据结构。

简单来区分的话,图分为有向图和无向图。有向图的边是有方向的,如果有A→B,则并不一定有B→A。但如果是无向图,则当A和B之间存在边时,一定是A↔B,即当A能走到B时,B也能走到A。

方便起见,引入一些基本术语:

结点的度:无向图中与结点相连的边的数目,称为结点的度。

结点的入度:在有向图中,以这个结点为终点的有向边的数目。

结点的出度:在有向图中,以这个结点为起点的有向边的数目。

权值:边的“费用”,可以形象地理解为边的长度。

连通:如果图中结点U,V之间存在一条从U通过若干条边、点到达V的通路,则称U、V 是连通的。

回路:起点和终点相同的路径,称为回路,或“环”。

完全图:一个n 阶的完全无向图含有n×(n-1)/2 条边;一个n 阶的完> > 全有向图含有n×(n-1)条边;

稠密图:一个边数接近完全图的图。

稀疏图:一个边数远远少于完全图的图。

需要注意,只有有向图才存在入度和出度的概念,在无向图中只有度而没有入度和出度。

图的存储结构

一般有两种实现方式,一种是邻接矩阵,另一种是邻接表。邻接邻接,相邻连接,连者为邻,互利互通。这个名字还是不难理解的。

邻接矩阵比较适合理解图的结构,具有直观,好写的优点。

定义二维数组G[][],对任意的G[i][j],代表从点i到点j的边的权值。如果该图的边无权,则只需要定义成0-1型就好。对于无向图,满足G[i][j] = G[j][i]。如果i与j之间不存在边,则定义为INF或者-1。(INF:infinity,即无穷,无限大,一般为2147483647,即int范围的最大值)

举例:

它们所对应的邻接矩阵如下:

建立邻接矩阵的代码模板:

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
#include <iostream>
#define maxn 2333
#define INF 2147483647
using namespace std;

int g[maxn][maxn];
int n, m;
int edgeNum;
int from, to, dis;
int main() {
cin >> n >> m >> edgeNum;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
g[i][j] = INF;
}
}
//初始化邻接矩阵,初始全部为INF表示全都不连通
for (int i = 1; i <= edgeNum; i++) {
cin >> from >> to >> dis;
g[from][to] = dis;
g[to][from] = dis; // 如果是有向图,这个语句就不能有
}
//此处请自由发挥
return 0;
}

快速初始化的方法:使用ctsdlib里面的memset函数对数组进行初始化,使用memset(g, 0x7f, sizeof(g))可以把数组全都初始化成一个很大的数,memset(g, 0, sizeof(g))全部初始化为0,memset(g, 0xaf, sizeof(g))初始化为一个很小的数。

然而,实际应用中邻接表使用的并不是很广泛,反而是邻接表使用较为广泛。

前置知识:链表的使用

邻接表存储法又叫图的链式存储法,它的原理是根据图上的每一个结点建立一个链表,在图上这个点每连接一个其他点,就把这个点的编号塞到链表后面,这样一个点与其连接的所有点就连成了一条链,将一张图上所有点的这个链弄出来排在一起,成为一个表状结构,就是邻接表。

举例:

这里只说下图A吧,B和C类似。对于V1,它连接V2,V3,V4,那么以V1为首的链表后面连接的结点就是V2,V3,V4(顺序不一定非得是这个,顺序只能表明先连的哪个点后连的哪个点。)对于V2,连接V1和V4和V3,对于V3,连接V2和V1,对于V4,连接V1和V2。画出图来大概是这样:

建立邻接表需要使用到结构体,它记录边的信息,一般是记录起止点和权值。然后开一个该结构体类型的数组代表的就是边集。你问点集怎么表示?点集不用表示。(想一想,为什么)

然后我们需要一个head数组,对于任意的head[i],代表的是以i点开头的链表的“位置”,这个位置是虚拟的,也正是这个数组模拟链表的关键所在。初学者在这里比较难以理解,简单来讲这可以用来代替链表的“指针域”进行存储。进行加边操作的时候需要对边数进行计数,from对应的是head[from],因为一个点为首的只有一条链表,这一步是找到这个链表的头,然后是to对to,dis对dis,最后更新一下head[from]为当前边数即可。严格来讲这个理解可能并不是很严谨,如果想深入理解可以查阅其他资料,或者选择基于实用主义,不求甚解。

建立邻接表的代码模板:

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
#include <iostream>
#define maxn 2333
using namespace std;
struct Edge {
int from, to, dis;
};
Edge edge[maxn];

int head[maxn], from, to, dis;
int totEdge = 0;
int n, m;

void addEdge(int from, int to, int dis) {
edge[++totEdge].from = head[from];
edge[totEdge].to = to;
edge[totEdge].dis = dis;
head[from] = totEdge;
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> from >> to >> dis;
addEdge(from, to, dis);
}
//此处请自由发挥
return 0;
}

最短路

引入带权图和无权图的概念。对于边有权值的图我们叫做带权图,否则叫做无权图。边的权值可以理解为两点之间的距离,或者移动的代价,花费等等。一张图中可能会有很多带有权值的路径把点连接起来,对于图的最短路,分为单源最短路和多源最短路。单源最短路指的是从一点出发到达图中某点的最短路径,多源最短路指的是任意两点之间的最短路。解决最短路径的算法有很多,但是每种算法都有一定的适用范围。

多源最短路:Floyed算法,多适用于邻接矩阵,时间复杂度O(n3),适用负边权

令dis[u][v]表示从u到v的最短路径长度,w[u][v]表示连接u,v边的长度。

首先初始化所有的dis,如果对于任意u,v有边相连则dis[u][v] = w[u][v],如果没有则dis[u][v] = INF。

算法过程:

1
2
3
4
5
6
7
8
for (int k = 1; k <= n; k++) { //这层循环必须放在最外面
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}

嗯,浑身上下散发着动态规划的味道。这的确是个动态规划,三层循环,第一层循环中间点k,第二第三层循环起点终点i、j,算法的思想很容易理解:如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离,那么就用这个更短的路径长度来更新原先点i到点j的距离。

假设现在有一无向图。有一条从点1到点2的带权边为6,有一条从点1到点3的带权边为2,有一条从点3到点2的带权边为1,可以知道dis[1][2] = 6,dis[1][3] = 2,dis[2][3] = 1,这是初状态。因为dis[1][3]+dis[3][2]<dis[1][2],所以就用dis[1][3]+dis[3][2]来更新原先1到2的距离。如果两者之间有最短路径的话,就会更新成最短路径的长度。

变形:

1
2
3
4
5
6
7
for (int k = 1; k <= n; k++) { //这层循环必须放在最外面
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
}
}
}

如果是一个没有边权的图,把相连的两点间的距离设为dis[i][j]=true,不相连的两点设为dis[i][j]=false,用这个办法可以判断一张图中的两点是否相连。

单源最短路:Dijkstra算法,多适用于邻接表,时间复杂度O(n2)(未经优化),O((n+m)logm)(加入堆优化),不适用负边权

也就是所谓的迪杰斯特拉算法。它是基于一个贪心的思想。从起点V0开始,每次新扩展一个距离最短的点,然后再以这个点为中间点去更新起点到其他所有点的距离。它无法处理边权有负的情况。由于所有的边权都是正,所以不会存在一个距离更短的没有扩展过的点。也就是说每次扩展都要保证路径是当前最短,所以当前这个点到起点的距离永远不会再被改变一次,从而保证算法的正确性。

设起点为s,dis[v]表示从s到v的最短路径,pre[v]为v的前驱节点,用来输出路径。首先初始化:dis[v]=∞(v≠s); dis[s]=0; pre[s]=0;

然后是伪代码:

for (i = 1 to n) {
    在没有被访问过的点中找一个顶点u使得dis[u]是最小的
    u标记为已确定最短路径
    for 与u相连的每个未确定最短路径的顶点v
        if (dis[u]+w[u][v] < dis[v]) {
            dis[v] = dis[u] + w[u][v];
            pre[v] = u;
        }
}

算法结束后,dis[v]为s到v的最短距离;pre[v]为v的前驱节点,用来输出路径。如果不需要pre数组的话可以不加。

这里为什么只给出了伪代码?因为实际使用的Dijkstra大多是优化之后的算法。

(以下文字摘自信息学奥赛一本通课件)

算法思想:从起点到一个点的最短路径一定会经过至少一个“中转点”(例如下图1到5的最短路径,中转点是2。特殊地,我们认为起点1也是一个“中转点”)。显而易见,如果我们想求出起点到一个点的最短路径,那我们必然要先求出中转点的最短路径(例如我们必须先求出点2 的最短路径后,才能求出从起点到5的最短路径)。换句话说,如果起点1到某一点V0的最短路径要经过中转点Vi,那么中转点Vi一定是先于V0被确定了最短路径的点。

我们把点分为两类,一类是已确定最短路径的点,称为“白点”,另一类是未确定最短路径的点,称为“蓝点”。如果我们要求出一个点的最短路径,就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。

Dijkstra的算法思想,就是一开始将起点到起点的距离标记为0,而后进行n次循环,每次找出一个到起点距离dis[u]最短的点u,将它从蓝点变为白点。随后枚举所有的蓝点vi,如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话,这将它作为vi的“更短路径”dis[vi](此时还不确定是不是vi的最短路径)。

就这样,我们每找到一个白点,就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点,故每一个终点一定能够被它的最后一个中转点所修改,而求得最短路径。

模拟这个过程,算法开始时,作为起点的dis[1] = 0,其他的点dis[i] = INF。

第一轮循环找到dis[1]最小,将1变成白点。对所有的蓝点做出修改,使得dis[2]=2,dis[3]=4,dis[4]=7。

第二轮循环找到dis[2]最小,将2变成白点。对所有的蓝点做出修改,使得dis[3]=3,dis[5]=4。这时dis[2],dis[3],dis[4]被它的最后一个中转点1修改为了最短路径。

第三轮循环找到dis[3]最小,将3变成白点。对所有的蓝点做出修改,使得dis[4]=4。发现以3为中转不能修改5,说明3不是5的最后一个中转点。这时dis[3],dis[5]被它们的最后一个中转点2修改为了最短路径。

接下来的两轮循环将4、5也变成白点。N轮循环结束后,所有的点的最短路径即能求出。这时dis[4]也被它的最后一个中转点3修改为了最短路径。

Dijkstra无法处理边权为负的情况。 比如下图这样的图:

2到3的边权值为-4,显然从起点1到3的最短路径是-2(1→2→3),但是dijskstra在第二轮循环开始时会找到当前dis[i]最小的点3,并标记它为白点。这时的dis[3]=1,然而1却不是从起点到点3的最短路径。因为3已被标记为白点,最短路径值dis[3]不会再被修改了,所以我们在边权存在负数的情况下得到了错误的答案。

堆优化:使用堆来优化查找操作。

堆优化之后的Dijkstra:(陈年老代码了,代码风格与现在略有不同)

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long
#define INF 2147483647
using namespace std;
int n,m,s,head[50010],cnt;
ll dis[10010];
bool used[10010];
struct Edge{
int to,from,dis;
}edge[500010];

void add_edge(int u,int v,int dis){
edge[cnt].to=v;
edge[cnt].from=head[u];
edge[cnt].dis=dis;
head[u]=cnt++;
}
typedef pair<int,int> P;
void dijkstra(int s){
priority_queue<P,vector<P>,greater<P> > q;
fill(dis,dis+n+1,INF);
fill(used,used+n+1,false);
dis[s]=0;
q.push(P(0,s));
while(!q.empty()){
P p=q.top();q.pop();
int u=p.second;
if(used[u]) continue;
used[u]=true;
int pp=head[u];
while(pp!=-1){
int v=edge[pp].to;
if(!used[v]&&dis[v]>dis[u]+edge[pp].dis){
dis[v]=dis[u]+edge[pp].dis;
q.push(P(dis[v],v));
}
pp=edge[pp].from;
}
}
}
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
add_edge(u,v,d);
}
dijkstra(s);
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
return 0;
}

单源最短路:Bellman-Ford算法(经过队列优化后的中国叫法是SPFA),多适用于邻接表,时间复杂度O(NE)(未经优化,N为点数,E为边数),O(kE)(k是常数,加入队列优化),适用负边权

同样是用来计算从一个点到其他所有点的最短路径的算法,也是一种单源最短路径算法。能够处理存在负边权的情况,但无法处理存在负权回路的情况。经过改造后的SPFA算法是笔者最喜欢也是最常用,同时也是最容易被卡的最短路算法。

(以下文字摘自信息学奥赛一本通课件)

设s为起点,dis[v]即为s到v的最短距离,pre[v]为v前驱。w[j]是边j的长度,且j连接u、v。初始化:dis[s]=0,dis[v]=∞(v≠s),pre[s]=0

for (i = 1; i <= n-1; i++)
    for (j = 1; j <= E; j++)    //注意要枚举所有边,不能枚举点。
       if (dis[u]+w[j]<dis[v]) {  //u、v分别是这条边连接的两个点。
           dis[v] =dis[u] + w[j];
           pre[v] = u;
      }

Bellman-Ford算法的思想很简单。一开始认为起点是白点(dis[1]=0),每一次都枚举所有的边,必然会有一些边,连接着白点和蓝点。因此每次都能用所有的白点去修改所有的蓝点,每次循环也必然会有至少一个蓝点变成白点。在下面这个简单的模拟中能看到白点的“蔓延”情况。

虽然Bellman-Ford算法可以求出存在负边权情况下的最短路径,却无法解决存在负权回路的情况。负权回路指一个环,这个环上所有的权值都为负,也可以理解成是指边权之和为负数的一条回路。如果图中出现负环会发生什么?

负权回路是指边权之和为负数的一条回路,上图中②-④-⑤-③-②这条回路的边权之和为-3。在有负权回路的情况下,从1到6的最短路径是多少?答案是无穷小,因为我们可以绕这条负权回路走无数圈,每走一圈路径值就减去3,最终达到无穷小。
所以说存在负权回路的图无法求出最短路径,Bellman-Ford算法可以在有负权回路的情况下输出错误提示。
如果在Bellman-Ford算法的两重循环完成后,还是存在某条边使得:dis[u]+w<dis[v],则存在负权回路:

for 每条边(u,v) 
    if (dis[u]+w<dis[v])  
        return false

优化:SPFA算法

SPFA算法在国际上通称为“经过队列优化的Bellman-Ford算法”,仅在中国流行SPFA这种名字。

设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路估计值对u点所指向的结点v进行松弛操作。如果v点的最短路估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断地从队列中取出结点来进行松弛操作,直到队列为空。这个算法保证只要最短路存在,SPFA算法必定能求出最小值。SPFA算法同样可以判断负环。额外设立一个inq数组,某个点入队的次数超过n次时,可以判断负环存在并且提前退出。

这个算法,简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法。

SPFA 在形式上和广度优先搜索非常类似,不同的是广度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是说一个点修改过其它的点之后,过了一段时间可能会获得更短的路径,于是再次用来修改其它的点,这样反复进行下去。
算法时间复杂度:O(kE),E是边数。K是常数,平均值为2。

SPFA代码模板:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 5000015
#define INF 2147483647
#define ms(x) memset(x,0,sizeof(x));
using namespace std;
struct Edge{
long long int from,to,dis;
};
Edge edge[maxn];
long long int n,m,s,u,v,d;
long long int head[maxn];
long long int dis[maxn];
bool inq[maxn];
long long int cnt = 0;
void add_edge(long long int from,long long int to,long long int dis){
edge[++cnt].from = head[from];
edge[cnt].to = to;
edge[cnt].dis = dis;
head[from] = cnt;
}

void spfa(void){
queue<long long int> q;
q.push(s);
ms(inq);
inq[s] = true;
for (int i=1;i<=n;i++)
dis[i] = INF;
dis[s] = 0;
while (!q.empty()){
long long int u = q.front();
q.pop();
inq[s] = false;
for (int i=head[u];i!=0;i=edge[i].from){
long long int v = edge[i].to;
long long int w = edge[i].dis;
if (dis[u]+w < dis[v]){
dis[v] = w+ dis[u];
if (!inq[v]){
q.push(v);
inq[v] = true;
}
}
}
}

}

int main(){
cin >> n >> m >> s;
for (int i=1;i<=m;i++){
cin >> u >> v >> d;
add_edge(u,v,d);
}
spfa();
for (int i=1;i<=n;i++)
cout << dis[i] << " ";
return 0;
}

该算法的速度非常之快,但当该算法运行在稠密图或者人为构造的网格图上,该算法的复杂度极有可能退化成O(NE)。

最小生成树(MST)

生成树的定义:在一个有n个点的无向图中,取其中n-1条边,连接所有的顶点,得到一个子图,这个子图便是原图的一个生成树。

为什么说子图是树?实际上,树是图的一种特殊形态。这里便扩充了一下图的定义:

图G是树当且仅当下面的任意一个条件成立:

1.G有n-1条边,不存在环

2.G有n-1条边,连通

3.G的任意两点之间只有唯一的简单路径。

4.G连通,但任意删除一条边后就不再连通。

引入最小生成树的概念:在一个带权的无向连通图中,各边权和最小的一棵生成树即为原图的最小生成树。

最小边原则:图中权值最小的边(如果唯一)一定在最小生成树上。

图的最小生成树的唯一性定理:对于一个图G,如果图中的边权值互不相同,则图中的最小生成树一定是唯一的,反之则不然。

最小生成树用来解决类似于使用最小代价用n-1条边连接n个点的问题。比如架设快速道路或者架设网线要求花费最少。

Prim算法 时间复杂度O(n2)


(以下文字摘自信息学奥赛一本通课件)

Prim算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想:白点代表已经进入最小生成树的点,蓝点代表未进入最小生成树的点。

算法描述:

以1为起点生成最小生成树,min[v]表示蓝点v与白点相连的最小边权。

MST表示最小生成树的权值之和。

a)初始化:min[v]= ∞(v≠1); min[1]=0;MST=0;
b)for (i = 1; i<= n; i++)
1.寻找min[u]最小的蓝点u。
2.将u标记为白点
3.MST+=min[u]
4.for 与白点u相连的所有蓝点v
if (w[u][v]<min[v])
min[v]=w[u][v];
c)算法结束: MST即为最小生成树的权值之和

算法分析&思想讲解:

Prim算法每次循环都将一个蓝点u变为白点,并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边,最后得到的一定是最小生成树。

算法证明:

①当只取了一个点K时(边集为空),一定存在一个MST,包含当前的点集和边集。

②假设存在一个MST包含当前的点集和边集。当前点集为S,剩下的点集为S’。设跨越S-S’的最小代价的边为(u,v)。

反证法:假设取的是跨越S-S’的某边(u’,v’),删除(u’,v’)加入(u,v),S和S’分别连通,且S-S’通过(u,v)也能连通,这样会得到一个更小权值的MST,所以新加入的边一定是代价最小的边(u,v)。

Q.E.D


Kruskal算法 时间复杂度O(ElogE)(E为边数)

前置知识:并查集

Kruskal(克鲁斯卡尔)算法是一种巧妙利用并查集来求最小生成树的算法。我们把无向图中相互连通的一些点称为处于同一个连通块中。Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合,那么就把这条边加入最小生成树,这两个不同的集合就合并成了一个集合;如果这条边连接的两个点属于同一集合,就跳过。直到选取了n-1条边为止。

算法描述:

初始化并查集。father[x]=x。
tot=0
将所有边用快排从小到大排序。
计数器 k=0;
for (i=1; i<=M; i++)      //循环所有已从小到大排序的边
  if  这是一条u,v不属于同一集合的边(u,v){ (因为已经排序,所以必为最小),
     ①合并u,v所在的集合,相当于把边(u,v)加入最小生成树。
     ②tot=tot+W(u,v)
      ③k++
      ④如果k=n-1,说明最小生成树已经生成,则break; 
  }
结束,tot即为最小生成树的总权值之和。

Kruskal在初始时认为所有的点都是孤立的。然后它枚举所有边(已按边权排好序),枚举到某边的时候会判断这条边连接的两点是否在同一集合里,如果不是则说明这条边一定在最小生成树里,则加入这一条边。一张n个点的图总共选取n-1次边。因为每次我们选的都是最小的边,所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合,最后n个点一定会合并成一个集合。通过这样的策略,Kruskal算法就能得到一棵有n-1条边,连接着n个点的最小生成树。

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
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
66
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 5005
#define maxm 200005
using namespace std;
struct Edge{
int from,to,dis;
bool operator <(const Edge &rhs)const{
return dis < rhs.dis;
}
};
Edge edge[maxm];
int father[maxm];
int n,m;
int totedge = 0;
int k = 0;
int ans = 0;
inline int read(){
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-')
flag = true;
else
num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
void init(){
for (register int i=1;i<=m;i++)
father[i] = i;
}
int find(int x){
if (father[x] == x)
return father[x];
father[x] = find(father[x]);
return father[x];
}

void merge(int x,int y){
father[find(x)] = find(y);
}

int main(){
n = read();m = read();
for (register int i=1;i<=m;i++){
edge[i].from = read();
edge[i].to = read();
edge[i].dis = read();
}
sort(edge+1,edge+m+1);
init();
while (totedge < n-1){
if (find(edge[++k].from) != find(edge[k].to)){
ans += edge[k].dis;
merge(edge[k].from,edge[k].to);
totedge++;
}
}
printf("%d\n",ans);
return 0;
}

拓扑排序

啥叫拓扑?百度百科这样说:

拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科。它只考虑物体间的位置关系而不考虑它们的形状和大小。拓扑英文名是Topology,直译是地志学,最早指研究地形、地貌相类似的有关学科。几何拓扑学是十九世纪形成的一门数学分支,它属于几何学的范畴。有关拓扑学的一些内容早在十八世纪就出现了。那时候发现的一些孤立的问题,在后来的拓扑学的形成中占着重要的地位。

简单来讲,拓扑研究的是图形的位置关系。而拓扑排序也就是指对一张有向无环图的所有点的次序进行排序,最后得到一个序列,而这个排序的规则便就是按照相连的先后顺序进行排序,这个排序就叫做拓扑排序。更简单的说,拓扑排序是把一个图变成一个序列。做成的这个序列就叫做拓扑序列。

引入新概念。

有向无环图(DAG):在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。

对拓扑排序的讨论均是建立在有向无环图上的。所以本栏目里面所说的图,如果不加特殊注明,均指有向无环图。构造拓扑序列可以帮助我们合理安排一个工程的进度,由DAG构造拓扑序列具有很高的实际应用价值。

举个最简单的例子,游戏的技能树就是一个很简单的有向无环图(之前说到,树也是图的一种)。假设有这么一个设定:所有的后续技能学习都需要一些前置技能的要求,也就是说如果你要学习一个新技能,必须要满足之前的某些技能是掌握的。那么对这个技能树进行拓扑排序,得到的就是一个拓扑序列,它代表着你先学了什么后学了什么。

而构造拓扑排序算法很简单。假如使用邻接表,需要稍稍改动一下加边函数,在里面统计一下某个点的入度,比如from a to b的一条边,一旦成立,b的入度就会+1。这样建图后我们可以得到一个数组,里面保存着各个点的入度信息。

然后我们扫描一下这个数组,寻找入度为0的点(如果保证原图是DAG,则这样的点一定存在)。把所有入度为0的点压入一个队列(不要只找到一个就结束这个操作,因为在DAG里可能存在多个入度为0的点)。

然后我们用一个while(!q.empty())控制循环。每次从队首取出一个结点(并且将这个结点弹出),这是当前遍历到的结点,将它输出(这里的输出并不是说非得要输出,因为题和题不一样,这里也有可能是其他操作,或者说是保存起来方便下一步操作),然后遍历所有与这个点连接的点(直接邻接表遍历操作就可以),把扫描到的点都入度-1,如果-1后入度变成了0,说明这应该是下一步要进行遍历的结点,就把这个结点入队。重复操作,直到队空为止,最后生成的序列就是拓扑序列。

比如说这个图,首先找到入度为0的点是只有A,把A入队。取队头是A,输出,弹出,然后遍历队头A的连接点,先找到B,入度-1后是0,入队,找到C,入度-1后是0,入队,D也是这样。一遍找完了,再回到开头取找队头,取队头是B,输出,弹出,然后遍历队头B的连接点,找到E,入度-1后变成2,不入队。找完B了找下一个队头是C,遍历C的连接点,找到E,入度-1后变成1。然后是D,这里再进行一步减入度的操作E的入度就变成了0,这里E就可以入队了。最后就是E。这样它的拓扑序列就是ABCDE。

Tips:使用队列那里并不强求,其实使用栈也是可以的。这也就意味着,一个DAG的拓扑序列可能不是唯一的。

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
#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 23333
using namespace std;
struct Edge {
int from, to, dis;
};
Edge edge[maxn];
int n, m, s, u, v, d;
int inDegree[maxn];
int tot = 0;
int head[maxn];

void addEdge(int from, int to, int dis) {
edge[++tot].from = head[from];
edge[tot].to = to;
edge[tot].dis = dis;
head[from] = tot;
inDegree[to]++; // update in-degree
}

void output(int u) {
cout << u << " ";
}

void topoSort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0)
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
output(u);
for (int i = head[u]; i; i = edge[i].from) {
int v = edge[i].to;
inDegree[v]--;
if (inDegree[v] == 0)
q.push(v);
}
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> d;
addEdge(u, v, d);
}
topoSort();
system("pause");
return 0;
}

强连通分量(已咕)

强连通:在一张图中存在有A到B的道路,同时也存在从B到A的道路,我们说这两个点强连通。

说人话:A和B强连通不能说明AB直接连通,只能说明可能有经过某些中间点的路,让点和点互相连通。当然,直接相连也是可以的。

强连通图:如果在一张图G中,有向图G的任意两个顶点都强连通,则说G是一个强连通图。

说人话:从任意点出发可以到达任意点,这种图就是强连通图。

强连通分量:有向非强连通图的极大强连通子图,称为强连通分量。

说人话:这是一个有向的图,它里边的点不能保证从任意点出发到达任意点。为什么要强调是有向图?因为如果是无向图,这种定义就没什么意义了啊。你想想,无向图里哪个点出发到不了任意点?也就只有度为0的孤点了。好的言归正传,

极大强连通子图:G是一个极大强连通子图,当且仅当G是一个强连通子图且不存在另一个强连通子图G’,使得G是G’的真子集。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:一本通提高篇学习笔记-图论基础

文章作者:Shawn Zhou

发布时间:2019年01月28日 - 19:01

最后更新:2019年03月10日 - 10:03

原始链接:http://shawnzhou.xyz/2019/01/28/19-01-28-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%