图论知识点全明星()

NOIP考前攒rp
图论是是数学的一个分支,图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。(这段话是摘抄的)

DFS(Depth First Search)

深度优先搜索,是处理很多问题是需要使用的方法,有时也是用来获得部分分的利器,一大特点就是递归调用其本身,也就是使用栈实现。

typename dfs(int u,...)
{
	if(conditions) return ...;
	give Tag;
	for(v to u)
	{
		if(visited) continue;
		dfs(v);
		details;
	}
	return ...;
}

DFS遍历而形成的树叫做DFS树,DFS树没有横插边。

BFS(Breadth First Search)

广度优先搜索,优先访问当前层的节点,一般使用队列实现。

typename bfs(int start_point,...)
{
	queue<typename> Q;
	Q.push_back(strat_point);
	details;
	while(!Q.empty)
	{
		u=Q.front();
		details;
		for(v to u)
		{
			if(visited) continue;
			details;
			Q.push_back(v);
		}
	}
	return ...;
}

树上问题

树的直径

树的直径是指树上任意两点间最长的简单路径。

两次DFS

第一次随机选择一个点,找到距离它最远的节点;再从这个节点为起点,到它深度最深的点。以这两个节点为端点的简单路径就是树的直径。
优势:实现简单

树形DP

首先假定一个点为根,对于每一个节点,维护以它为根的子树内,经过根的最长路径和从叶子到根的最长路径,然后进行转移。
优势:可以进行修改,实现更丰富。

最近公共祖先 LCA

倍增跳写法

对于每个节点。维护它的所有 \(2^i\) 级祖先 \(i=0,1\dots \log n\) 。查找两个点的祖先时,先将深度大的节点跳到和深度小的节点深度相同,让后两个节点同时向上跳找lca。
算法时间复杂度 \(O(n\log n+Q\log n)\) ,空间复杂度 \(O(n\log n)\) 。

树剖写法

首先对整棵树进行重链剖分,当询问的两个节点不在同一条链的时候,选择链顶深度更深的那个节点,跳到链顶的父亲,重复此过程直到在同一条链中,返回深度更小的点。
算法时间复杂度 \(O(n+Q\log n)\) ,空间复杂度 \(O(n)\) 。

ST表写法

对整个树进行一次 \(dfs\) ,按照访问顺序将它以深度为第一关键字,节点为第二关键字变成长度为 \(2n\) 的序列,对这个序列预处理ST表。每次询问极为查询区间最小值的第二关键字。
算法时间复杂度 \(O(n\log n+Q)\) ,空间复杂度 \(O(n\log n)\) 。

LCT写法(基本上没有这样的吧)

每个节点存储以深度为第一关键字,编号为第二关键字的二元组,每次查询一条链上最小值的第二关键字。
算法时间复杂度 \(O(n+Q\log n)\) ,空间复杂度 \(O(n)\) 。

树的重心

对于某一个节点,如果它每一个子树的大小均不超过树大小的一般,这个点就是树的重心。

dfs求重心

DFS是维护每个子树的大小,就可以得到以每个节点为根时的所有子树大小,然后判断即可。
算法时间复杂度 \(O(n)\) 。

最小生成树

一个无向图图边权和最小的生成树成为最小生成树。

Kruskal算法

对所有的边进行排序,依次加入最小的边,同时用并查集维护图的连通性。
算法复杂度 \(O(m\log m+m \log n)\) 。

Prim算法

首先选择一个点,然后依次向这个连通块内加入到这个连通块距离最短的点即可。
使用堆维护,复杂度为 \(O(n\log n+m\log n)\) 。

最短路

Floyd 算法

memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=0;
for(int i=1;i<=m;i++) f[l[i].u][l[i].v]=f[l[i].v][l[i].u]=l[i].len;
for(int k=1;k<=n;k++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
	f[u][v]=min(f[u][v],f[u][k]+f[k][v]);

SPFA

struct edge{
	int poi,len;
};
vector<edge> e[MAXN];
queue<int> Q;
int dis[MAXN],cnt[MAXN],vis[MAXN];
bool SPFA(int s)
{
	memset(dis,0x3f,sizeof(dis));
	int u=0;
	dis[s]=0,vis[s]=true;
	Q.push(s);
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop(),vis[u]=false;
		for(int k=0,lim=e[u].size(),v,w;k<lim;k++)
		{
			v=e[u].poi,w=e[u].len;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n) return false;
				if(!vis[v]) Q.push(v),vis[v]=true;
			}
		}
	}
	return true;
}

SPFA判负环

struct edge{
	int poi,len;
};
vector<edge> e[MAXN];
queue<int> Q;
long long dis[MAXN];
int cnt[MAXN];
bool vis[MAXN];
int n,m,s,i,u,v,w;
bool SPFA(int s)
{
	int u=0;
	for(int i=1;i<=n;i++) dis[i]=2147483647;
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[s]=0,vis[s]=true;
	while(!Q.empty()) Q.pop(); 
	Q.push(s);
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop(),vis[u]=false;
		for(int k=0,lim=e[u].size(),v,w;k<lim;k++)
		{
			v=e[u][k].poi,w=e[u][k].len;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v]) 
				{
					Q.push(v),vis[v]=true;
					cnt[v]++;
					if(cnt[v]>=n) return false;
				}
			}
		}
	}
	return true;
}

Dijkstra 算法

typedef pair<int,int> pr;
vector<pr> e[MAXN];
long long dis[MAXN];
bool vis[MAXN];
priority_queue<pr,vector<pr>,greater<pr> > Q;
void Dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	Q.push(make_pair(0,s));
	while(!Q.empty())
	{
		int u=Q.top().second;
		Q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(auto ed:e[u])
		{
			int v=ed.first,len=ed.second;
			if(dis[v]>dis[u]+len)
			{
				dis[v]=dis[u]+len;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
	return;
}
————————

NOIP考前攒rp
图论是是数学的一个分支,图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。(这段话是摘抄的)

DFS(Depth First Search)

深度优先搜索,是处理很多问题是需要使用的方法,有时也是用来获得部分分的利器,一大特点就是递归调用其本身,也就是使用栈实现。

typename dfs(int u,...)
{
	if(conditions) return ...;
	give Tag;
	for(v to u)
	{
		if(visited) continue;
		dfs(v);
		details;
	}
	return ...;
}

DFS遍历而形成的树叫做DFS树,DFS树没有横插边。

BFS(Breadth First Search)

广度优先搜索,优先访问当前层的节点,一般使用队列实现。

typename bfs(int start_point,...)
{
	queue<typename> Q;
	Q.push_back(strat_point);
	details;
	while(!Q.empty)
	{
		u=Q.front();
		details;
		for(v to u)
		{
			if(visited) continue;
			details;
			Q.push_back(v);
		}
	}
	return ...;
}

树上问题

树的直径

树的直径是指树上任意两点间最长的简单路径。

两次DFS

第一次随机选择一个点,找到距离它最远的节点;再从这个节点为起点,到它深度最深的点。以这两个节点为端点的简单路径就是树的直径。
优势:实现简单

树形DP

首先假定一个点为根,对于每一个节点,维护以它为根的子树内,经过根的最长路径和从叶子到根的最长路径,然后进行转移。
优势:可以进行修改,实现更丰富。

最近公共祖先 LCA

倍增跳写法

对于每个节点。维护它的所有 \(2^i\) 级祖先 \(i=0,1\dots \log n\) 。查找两个点的祖先时,先将深度大的节点跳到和深度小的节点深度相同,让后两个节点同时向上跳找lca。
算法时间复杂度 \(O(n\log n+Q\log n)\) ,空间复杂度 \(O(n\log n)\) 。

树剖写法

首先对整棵树进行重链剖分,当询问的两个节点不在同一条链的时候,选择链顶深度更深的那个节点,跳到链顶的父亲,重复此过程直到在同一条链中,返回深度更小的点。
算法时间复杂度 \(O(n+Q\log n)\) ,空间复杂度 \(O(n)\) 。

ST表写法

对整个树进行一次 \(dfs\) ,按照访问顺序将它以深度为第一关键字,节点为第二关键字变成长度为 \(2n\) 的序列,对这个序列预处理ST表。每次询问极为查询区间最小值的第二关键字。
算法时间复杂度 \(O(n\log n+Q)\) ,空间复杂度 \(O(n\log n)\) 。

LCT写法(基本上没有这样的吧)

每个节点存储以深度为第一关键字,编号为第二关键字的二元组,每次查询一条链上最小值的第二关键字。
算法时间复杂度 \(O(n+Q\log n)\) ,空间复杂度 \(O(n)\) 。

树的重心

对于某一个节点,如果它每一个子树的大小均不超过树大小的一般,这个点就是树的重心。

dfs求重心

DFS是维护每个子树的大小,就可以得到以每个节点为根时的所有子树大小,然后判断即可。
算法时间复杂度 \(O(n)\) 。

最小生成树

一个无向图图边权和最小的生成树成为最小生成树。

Kruskal算法

对所有的边进行排序,依次加入最小的边,同时用并查集维护图的连通性。
算法复杂度 \(O(m\log m+m \log n)\) 。

Prim算法

首先选择一个点,然后依次向这个连通块内加入到这个连通块距离最短的点即可。
使用堆维护,复杂度为 \(O(n\log n+m\log n)\) 。

最短路

Floyd 算法

memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=0;
for(int i=1;i<=m;i++) f[l[i].u][l[i].v]=f[l[i].v][l[i].u]=l[i].len;
for(int k=1;k<=n;k++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++)
	f[u][v]=min(f[u][v],f[u][k]+f[k][v]);

SPFA

struct edge{
	int poi,len;
};
vector<edge> e[MAXN];
queue<int> Q;
int dis[MAXN],cnt[MAXN],vis[MAXN];
bool SPFA(int s)
{
	memset(dis,0x3f,sizeof(dis));
	int u=0;
	dis[s]=0,vis[s]=true;
	Q.push(s);
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop(),vis[u]=false;
		for(int k=0,lim=e[u].size(),v,w;k<lim;k++)
		{
			v=e[u].poi,w=e[u].len;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n) return false;
				if(!vis[v]) Q.push(v),vis[v]=true;
			}
		}
	}
	return true;
}

SPFA判负环

struct edge{
	int poi,len;
};
vector<edge> e[MAXN];
queue<int> Q;
long long dis[MAXN];
int cnt[MAXN];
bool vis[MAXN];
int n,m,s,i,u,v,w;
bool SPFA(int s)
{
	int u=0;
	for(int i=1;i<=n;i++) dis[i]=2147483647;
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[s]=0,vis[s]=true;
	while(!Q.empty()) Q.pop(); 
	Q.push(s);
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop(),vis[u]=false;
		for(int k=0,lim=e[u].size(),v,w;k<lim;k++)
		{
			v=e[u][k].poi,w=e[u][k].len;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v]) 
				{
					Q.push(v),vis[v]=true;
					cnt[v]++;
					if(cnt[v]>=n) return false;
				}
			}
		}
	}
	return true;
}

Dijkstra 算法

typedef pair<int,int> pr;
vector<pr> e[MAXN];
long long dis[MAXN];
bool vis[MAXN];
priority_queue<pr,vector<pr>,greater<pr> > Q;
void Dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	Q.push(make_pair(0,s));
	while(!Q.empty())
	{
		int u=Q.top().second;
		Q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(auto ed:e[u])
		{
			int v=ed.first,len=ed.second;
			if(dis[v]>dis[u]+len)
			{
				dis[v]=dis[u]+len;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
	return;
}