图论笔记

图

图的定义

图G是一个有序二元组(V,E)，其中V称为点集，E称为边集

无向图、有向图：

无向图：所有边都是无向边

有向图：存在一条边是有向的图

(上文为简单理解)

图的概念

**度：**一个顶点的度指的是与该顶点相关联的边的边的条数，顶点v的度称为d(v).

**入度、出度：**对于有向图来说，一个顶点的度可以细分为入度和出度。一个顶点的入度指的是与其相关联的各边中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

**自环：**如果一条边的两个顶点为同一顶点，那么这个边就称为自环

**路径：**在一个图上遍历，所遍历的点叫路径

**环：**如果路径的出发点和路径的结束点一样，那么这个路径就叫做环

**简单路径：**每个点最多只走一次的路径，在简单路径中，点是不可以重复的

**简单环：**去掉起点之后，是一个简单路径，这样的环叫做简单环

特殊的图

**没有环的无向图（无环无向连通图）：**树

n个点的树有n-1条边

—>无环无向图：森林

—>无环连通图：外向树、内向树

**外向树：**树上的的所有边的方向都是向叶子节点指的

**内向树：**树上的所有边的方向都是向根节点指的

树的拓展：

**章鱼图：**中间只有一个环，周边伸展出去都是一棵树的图，又称“基环树”

怎么把这个图变成一棵树呢？

将环断掉，删去环上的任意一条边就可以变成一棵树了。

如何把一棵树变成一个章鱼图呢？

随便加一条边即可。

**章鱼图Dp的做法：**两个DP，一个树形DP，一个环形DP，先树形Dp，再环形DP

如何在章鱼图上找环？

深度优先搜索，一直，直到走到了它的某一个祖先，这样它和它的祖先之间就形成了一个环

**仙人掌图：**边仙人掌和点仙人掌

**边仙人掌：**有很多个环，每个环对应树的一个边

点仙人掌：有很多个环，每个环对应树的一个节点

**DAG:**有向无环图（多半是一个Dp的题目）

**二分图：**如果一个图有奇环，是二分图，如果没有奇环，那一定是二分图

如果两个相邻的两个点通过染不同的颜色，只有一种染色方法，那么这就是二分图

图的储存方法

邻接矩阵：

好处：非常非常快，判断边的存在只需要O(1)的时间

坏处：空间过大

边表：

用链表来存储所有的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct edge
{
	int e,next;//next代表下一条边的边号是多少 、e表示终点 
}ed[maxm];

int en,first[maxn];//en代表边的数量 first从i出发的第一个边的编号 

void add_edge(int s,int e)
{
	en++;
	ed[en].next=first[s];
	first[s]=en;
	ed[en].e=e;
}

for(int p=first[1];p!=0;p=ed[p].next)
ed[p].e;

最短路问题

**单源最短路径：**求一点到所有点的最短路

**多源最短路径：**求多点到所有点的最短路

FLOYD

1
2
3
4
5
6
7
8
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j++)
	{
		for(int k=1;k<=n;k++)
		f[j][k]=min(f[j][k],f[j][i]+f[i][k]); 
	}
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
void dijkstra()
{
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	for(inr i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		if(!right[j]&&(p==-1||dist[p]>dist[j])) p=j;
		right[p]=true;
		for(int j=first[p];j;j=ed[j].next)
       dist[ed[j].e]=min(dist[ed[j].e],dist[p]+ed[j].d);
	}
}

堆优化

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
//dijkstra 的堆优化 
#include <queue>
using namespace std;
struct point{
	int p,d;
	point(){p=d=0;}
	point(int a,int b){p=a;d=b;}
};
bool operator<(const point &a,const point &b)
{
	retuern a.d>b.d;
}
priority_queue<point> heap;

void dijkstra(int s)
{
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	for(int i=1;i<=n;i++)
	heap.push(point(i,dist[i]));
	for(int i=1;i<=n;i++)
	{
		while(right[heap.top().p])
		heap.pop();
		point now=heap.top();
		heap.pop();
		int p=now.p,d=now.d;
		right[p]=true;
		for(int j=first[p];j!=0;j=ed[j].next)
		{
			int e=ed[j].e;
			int d=dist[p]+ed[j].d;
			if(dist[e]>d)
			{
				dist[e]=d;
				heap.push(point(e,d));
			}
		}
	}
}

Bellman-Ford

1
2
3
4
5
6
7
8
9
for(int i=1;i<=m;i++)
{
	cin>>s[i]>>e[i]>>d[i];
}
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
dist[e[j]]=min(dist[e[j]],dist[s[j]]);

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
void spfa(int s)
{
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		now=q.top;
		q.pop();
		
		for(int i=first[now];i;i=ed[i].next)
		{
			int e=ed[i].e;
			int d=dist[now]+ed[i].d;
			if(dist[e]>d)
			{
				dist[e]=d;
				if(!=inque[e])
				inque[e]=true,q.push(e);  
			}
		}
	}
}

负环的判定

1.最短路经过边数不能大于n-1

2. SPFA 任何一个点入队次数不能超过n次

差分约束

给定n个变量和m个不等式

xi−xj≤akx_i-x_j \leq a_k

求xn−x1x_n-x_1的最大值

解法：

xi−xj≤a,xj−xk≤b→xi−xk≤a+bx_i-x_j \leq a ,x_j-x_k \leq b \rightarrow x_i-x_k \le a+b

记录yiy_i表示到第i个点的最短路

则有

yi≤yj+a,yj≤yk+b→yi≤yk+a+by_i \le y_j+a,y_j \le y_k+b \rightarrow y_i \le y_k +a+b

最大值对应最短路，最小值对应最长路

树相关

**树的储存方式：**当做一个无向图去存

树最上面的节点叫根，最下面的节点叫做叶子

最近公共祖先问题（LCA）：

给你两个点，这两个点都有他们的祖先，他们的公共祖先是这两个点祖先的交集，所有公共祖先最靠下的一点叫做最近公共祖先。

作用

确定树上一条路径

LCA的求法

暴力

两个点往上跳，找出各自的祖先，得到它们最深的一个交点就是最近公共祖先

如果两个点深度相等

可以倍增跳；

----->倍增求LCA

倍增求LCA

设立状态

F i j 表示i这个点向上跳2j2^j步能到的点

可以看做先跳2j−12^{j-1}，再跳2j−12^{j-1}步，这样这个问题就可以解决了

既

F i j=F [F i j-1] j-1

步骤：

1.调整深度

2.一起跳

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
//预处理 
void dfs(int now)
{
	for(int p=first[now];i;i=ed[i].next)
	if(ed[i].e!=f[now][0])
	{
		int p=ed[i].e;
		depth[p]=depth[now]+1; 
		int f[p][0]=now;
		for(int x=1;x<=18;x++)
		f[p][x]=f[f[p][x-1]][x-1];
		dfs(p);
	}
}
int get_lca(int p1,int p2)
{
	if(depth[p1]<depth[p2])
	for(int x=18;x>=0;x--) 
	{
		int p=f[p1][x];
		if(depth[p]>=depth[p2]) p1=p;
	}
	if(p1==p2) return p1;
	for(int x=18;x>=0;x--)
	if(f[p1][x]!=f[p2][x])
	p1=f[p1][x],p2[p2][x];
	return f[p1][0];
}

树的序列化

dfs序

按照深度优先搜索的顺序遍历的点所组成的序列叫做dfs序

预处理dfs序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int now,int f)
{
	q[l[now]]=now;//q表示dfs序列 
	int x=l[now]+1;
	size[now]=1;
	for(int i=first[now];i;i=ed[i].next )
	if(ed[i].e!=f)
	{
		l[e->e]=x;
		dfs(ed[i].e);
		x=r[ed[i].e]+1;
		dfs(ed[i].e);
		size[now]+=size[ed[i].e];
	}
	r[now]=l[now]+size[now]-1;
}

l[1]=1,r[1]=n;

bfs求dfs序

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
int front=1,tail=1;
q[1]=1;
for( ;front<=tail;)
{
	int now=q[front++];
	for(int i=first[now];i;i=ed[i].next)
	if(!vis[ed[i].e])
	{
		q[++tail]=ed[i].e;
		vis[ed[i].e]=true;
	}
}
for(int i=n;i>=1;i--)
{
	int now=q[i];
	size[now]=1;
	for(int i=first[now];i;i=ed[i].next )
	if(size[ed[i].e])
	size[now]+=size[ed[i].e];
}
l[1]=1;r[1]=n;
for(int i=1;i<=n;i++)
{
	int now=q[i];
	int x=l[now]+1;
	for(int i=first[now];i;i=ed[i].next)
	if(size[ed[i].e]<size[now])
	{
		l[ed[i].e]=x;
		r[ed[i].e]=l[ed[i].e]+size[ed[i].e]
		x=r[ed[i].e]+1;
	}
}
for(int i=1;i<=n;i++)
q[l[i]]=i;

括号序列

生成树

一个图变成一个树

最小生成树

找到一棵生成树，使得这些边的边权总和最小

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void prim(int s)
{
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	for(int i=1;i<=n;i++)
	{
		int p=-1;
		for(int j=1;j<=n;j++)
		if(!right[j]&&(p==-1||dist[p]>dist[j])) p=j;
		right[p]=true;
		for(int j=first[p];j;j=ed[j].next)
		dist[ed[j].e]=min(dist[ed[j].e],ed[j].d);
	}
}

优化和Dijkstra 非常相似

Kruscal

使用并查集来做

求次小生成树

可以由最小生成树替换一条边得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//并查集求最大链
int get_max(int p1,int p2)
{
	p1=get_f(p1);
	p2=get_f(p2);
	int ans=-23333;
	while(p1!=p2)
	{
		if(depth[p1]<depth[p2])
		swap(p1,p2);
		ans=max(ans,fd[p1]);//fd代表到父亲的长度
		merge(p1,f[p1]);
		p1=get_f(p1);
	}
	return ans; 
}

连通分量

如果一个子图，从其中任意一个点出发，可以到达这个图的任意一个点，这个连通分量就叫做强连通分量

求强连通分量

Tarjan求强连通分量

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
void dfs(int now)
{
	t++;//找到了一个新的点 
	dfn[now]=low[now]=t;//dfn代表dfs的顺序，low表示从i点出发，可以向下走或者走回边
	//能走到的所有点中dfn值最小是多少 ,赋值为t是因为它最先走到它自己 
	s[++size]=now;//储存当前点的祖先或在环里面且为确定为连通分量的点 
	instack[now]=true;
	for(int i=first[now];i;i=ed[i].next)
	{
		int e=ed[i].e;
		if(!dfn[e])
		{
			dfs(e);
			low[now]=min(low[now],low[e]);//e能走到的所有点now也可以走到 
		}
		else
		{
			if(instack[e])
			low[now]=min(low[now],dfn[e]);
			//还没有从栈里面弹出来，所以他的祖先在栈里面，这是一条回边 
		}
	 }
	 if(dfn[now]==low[now])//如果自己dfn值和low值一样，要取出这个点了 
	 {
	 	cnt++;
	 	belong[now]=cnt;//now 这个节点属于新的连通分量 
	 	while(s[size]!=now)//在栈now后面的都属于和now的同一个强连通分量 
	 	{
	 		belong[s[size]]=now;
	 		instack[s[size]]=false;
	 		size--;
		 }
		 size--;
		 instack[now]=false;
	 }
}

作用

缩点，然后变成有向无环图（DAG），然后做dp,点权和边权规定到相应的强连通分量中

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
if(!dfn[i]) dfs(i);

for(int i=1;i<=n;i++)
	for(int j=first[i];j;j=ed[j].next)
	if(belong[i]!=belong[ed[j].e])
	add_edge2(belong[i],belong[ed[j].e]);

拓扑排序

**目的：**使转移始终从左向右进行

**方法：**每次找到一个入度为0的点，然后删去，不断重复这一过程，被删去点的先后顺序即为拓扑排序的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int size=0;
for(int i=1;i<=n;i++)
if(!in[i])
{
	size++;
	q[size]=i;
}

for(int i=1;i<=n;i++)
{
	int now=q[i];
	for(int j=first[now];j;j=ed[j].next)
	{
		int e=ed[j].e;
		in[e]--;
		if(!in[e])
		{
			size++;
			q[size]=e;
		} 
	}
}

2 SAT问题（判定性问题）

无向图中的问题

**桥：**在无向图中，删掉这一条边，使这个无向图不连通，那么这一条边叫做桥

**割点：**删掉这个点，使这个图不连通，那么这个点叫做割点

**边双连通分量：**这个子图尽量大，且这个图里面没有桥

**点双连通分量：**这个子图尽量大，且这个图里面啊没有割点

如果一个图里面有k个桥，那么这个图里面有k+1个边双连通分量

边双连通分量，缩点后可以看成一个树

求边双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
dfn[2333],low[2333];//和tarjan的相同 
void dfs(int now,int from)//from指的是当前从那一条边走过来的 
{
	t++;
	dfn[now]=low[now]=t;
	vis[now]=true;
	for(int i=first[now];i;i=ed[i].next)//一条无向边会被拆为两条有向边形成死循环 
	if((i^1)!=from)
	{
		int e=ed[i].e;
		if(!dfb[e])
		{
			dfs(e,i);
			low[now]=min(low[now],low[e]);
		}
		else
		{
			if(vis[e])
			low[now]=min(low[now],dfn[e]);
		}
	}
	vis[e]=false;
}

二分图问题

回顾二分图：左边有n个点，右边有m个点，左边内部没有边，右边内部也没有

**匹配：**如果说左边的i和右边的j连接了一条边，那么这两个点可以匹配，每个点最多只能和一个点匹配

匈牙利算法求最大二分图匹配

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
int n,m;//左边有n个人，右边有m个人 

bool dfs(int i)//让左边第i个人尝试匹配，看是否成功 
{
	for(int j=1;j<=m;j++)
	if(match[i][j]&&!use[j])
	{
		use[j]=true;
		if(!result[j]||dfs(result[j]))//result[i]表示右边的i和左边的某个数匹配 
		{
			result[j]=i;
			return true;
		}
	}
	return false;
}
int xiongyali()
{
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memset(use,false,sizeof(use));
		if(dfs(i)) ans++;//匹配成功就把答案加一 
	}
	return ans;
}

最大独立集

选择尽量多的点，使这几个点之间都没有边相连，这就是最大独立集

最大团

从一个图中选择尽量多的点，每个点之间都必须连边，这就是最大团

最大团与最大独立集的关系

最大团等于补图的最大独立集

它们都是NPC的问题

在二分图上我们可以求最大独立集

最大独立集→\rightarrow二分图

最大团→\rightarrow二分图的补图

最大独立集和最大匹配之和等于点数

类似于最大流等于最小割