【算法学习】图论模板

注意！

• 并查集只适用于无向图。

DFS

特点：当前层可以获得下层状态、向下层不断遍历

处理方式：递归

模板:

// dfs注意剪枝
void dfs(int u){
    if(u > n)
    {
        输出路径
        return;
    }
    for(int i = 0; i < n;i ++) // 遍历点
    {
        if(条件)
        {
            st[i] = true; // 标记已使用
            dfs(u + 1); //进行下一层递归
            st[i] = false; //还原状态
        }
    }
}

BFS

特点：可以得到点之间的距离、优先遍历当前层

处理方式：队列

模板：

int bfs(){
    queue<int或PII> q;
    q.push(初始点)
    点的初始化，如dist[1] = 0;
    while(q.size()) //只要队列不空就一直循环
    {
        auto t = q.front();
        q.pop;
        遍历点
        {
            if(条件)
            {
                修改点的属性，比如dist[i] = t + 1;
                q.push(当前点)
            }
        }
    }
}

树和图

树就是特殊的图，因此树相关的问题可以用图来做

存储方式：邻接矩阵(稠密图)、邻接表(稀疏图)

int e[N],ne[N],h[N],idx; // e存储边idx指向的点，ne存储当前边idx的下一条边，h存储点的第一条边

void add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a], h[a] = idx++; // 让边idx指向点b，边idx的下一条边变为a的第一条边，a的第一条边变为idx++(注意这并不会影响到ne[idx]的值)
}

memset(h,-1,sizeof h); //初始化h

树和图的深度遍历

适用于：边权为1

处理方式：递归点

bool st[N];

void dfs(int u)
{
	特判
	st[u] = true;
	for(int i = h(u); i != -1; i = ne[i])
	{
		int j = e[i];
		if(条件){
			dfs(j); // 注意是递归的点
		}
	}
	st[u] = false;
}

树和图的广度遍历

适用于：边权为1

处理方式：队列

bool st[N];
queue<pair<int,int> > q;
int dist[N];

int bfs()
{
	// 初始化
	q.push(初始值)
	dist[1] = 初始值;
	while(q.size()){
		auto t = q.front();
		q.pop();
		获取下标ver
		for(int i = h[ver];i != -1;i = ne[i]){
			int j = e[i];
			if(!st[j]){
				更新dist
				q.push(新值);
			}
		}
	}
	
	return dist[n] // 根据题目需要，这里返回的是n到1的距离
}

朴素dijkstra

适用于：边权为正，求最短路

/*
流程
for循环n次{
	1.找出不在已经确定的距离最近的点的集合中的点
	2.将该点加入集合中
	3.用该点更新其他点的距离
}
*/

int n; // 点的个数
bool st[N]; //st是已经确定的距离最近的点的集合
int dist[N]; // 点的距离

int dijkstra(){
	for(int i = 0; i < n;i ++){	// for循环n次
		// 找出不在st中的距离最近的点
		int t = -1;
		for(int j = 1; j <= n;j ++){
			if(!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		}
		
		// 将该点加入集合中
		st[t] = true;
		
		// 用该点更新其他点的距离
        for(int j = 1; j <= n;j ++)
		{
			if(!st[t] && dist[j] > dist[t] + g[t][i])
				dist[j] = dist[t] + g[t][i];
		}
	}
	return dist[n];
}

堆优化dijkstra

特点：在朴素dijkstra算法的基础上，将步骤1(找出不在已经确定的距离最近的点的集合中的点)优化为用小根堆(priority_queue)来找

适用于：边权为正，求最短路

int e[N],ne[N],h[N],w[N],idx;
int dist[N];
bool st[N]; // 已经确定的距离最短的点的集合
priority_queue<PII,vector<PII>, greater<PII> > heap; // 优先队列做小根堆

int dijkstra() {
	dist[1] = 0;
	// 将第一个点入堆
	heap.push({0,1});
	while(heap.size()) {
		// 每次堆都会弹出最小的值
		auto t = heap.top();
		heap.pop();
		int ver = t.second,distance = t.first;
		// 判断是否为不在已经确定距离的点的集合的距离最小的点
		if(st[ver]) continue;
		st[ver] = true;
		for(int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if(!st[j] && dist[j] > dist[ver] + w[i])
				dist[j]  = dist[ver] + w[i];
				heap.push({dist[j],j});
		}
		
	}
	判断是否成功
	return dist[n];
}

bellman_ford

适用于：求最短里、判断负环

/*
两重for循环:
	第一重for循环，循环k次，表示最多经过k条边的最短距离
	第二重for循环，循环m次，表示将所有的边枚举，并更新终点的距离
*/

int n,m,k;
int dist[N],backup[N];

struct Edge
{
	int a,b,w;
}edges[M];

int bellman_ford(){
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0;
	
	for(int i = 0; i < k;i ++){
		// 备份上一次的状态
		memcpy(backup,dist,sizeof dist);
		for(int j = 0; j < m;j ++)
		{
			int a = edges[j].a,b = edges[j].b,w = edges[j].w;
			// 因为dist[a]有可能被更新，所以用上一个的状态去更新dist[b]
			if(dist[b] > backup[a] + w){
				dist[b] = backup[a] + w;
			}
		}
	}
	if(dist[n] > 0x3f3f3f3f / 2) return -2;
	return dist[n];
}

spfa

适用于：求最短路、判断负环

/*
将元素加入队列
while(队列不空){
	将元素移除队列
	用元素更新其他点，并将被更新的点加入队列
}
*/
int n,m;
int e[N],ne[N],h[N],w[N],idx;
queue<int> q;
bool st[N];  // 判断是否在队列中
int dist[N];

int spfa(){
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0；
	q.push(1);
	st[1] = true; // 将元素加入队列
	while(q.size()){
		auto t = q.front();
		q.pop();
		st[t] = false; // 将元素移除队列
		for(int i = h[a]; i != -1;i ++)
		{
			int j = e[i];
			// 如果该点距离被更新就将它加入队列
			if(dist[j] > dist[t] + w[i]){
				dist[j] = dist[t] = w[i];
				if(!st[j]){
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	
	
	if(dist[n] > 0x3f3f3f3f / 2) return -2;
	return dist[n];
}

floyd

适用于：求最短路

/*
三重for循环
f[i][j] = min(f[i][j],f[i][k] + f[k][j]);

注意初始化
*/

int n, m;
int f[N][N];

void floyd(){
	// 三重循环k i j
	for(int k = 1; k<= n ;k ++)
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= n;j ++)
				// 注意公式
				f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
}

int main(){
	// 初始化f数组
	for(int i = 1; i <= n ;i ++)
		for(int j = 1; j <= n;j ++)
			if(i == j) f[i][j] = 0;
			else f[i][j] = INF;
			
    while(m--)
	{
		int a,b,c;
		cin >> a >> b >> c;
		f[a][b] = min(f[a][b],c);
	}
}

prim(加点法)

适用于：求最小生成树

/*
两重for循环:
	第一重for循环从0到n-1
		第一重for循环从1到n(枚举所有的点)
			找出距离集合距离最近的点
		判断是否连通
		第一重for循环从1到n
			用这个点去更新其他不在集合中的点到集合的距离
		将该点加入集合
*/

int n,m;
int g[N][N]; // 邻接矩阵
bool st[N]; // 判断是否在集合中
int dist[N]; // 点到集合的距离

int prim(){
	memset(dist, 0x3f,sizeof dist);
	dist[1] = 0; // 初始化
	int res = 0;
	for(int i = 0;i < n;i ++){ //第一重循环
		// 找距离集合最近的点
		int t = -1;
		for(int j = 1; j <= n;j ++)
			if(!st[j] && (t == -1 || dist[j] > dist[t]))
				t = j;
		// 判断是否连通
		if(i && dist[t] == INF) return INF;
		// 加权，用来返回最小生成树的权值，一定要在更新前加，因为后面的更新可能会导致权重改变
		if(i) res += dist[t];
		// 用这个点去更新其他不在集合中的点到集合的距离
		for(int j = 1; j <= n;j ++){ //第二重循环
			if(!st[j] && dist[j] > g[t][j])
				dist[j] = g[t][j];
		}
		st[t] = true; // 将该点加到集合中去
	}
	return res;
}

Kruskal(加边法)

搭配：并查集

适用于：求最小生成树

/*
将所有边按升序排序
从小到大枚举所有的边
	如果边的两个点不在一个集合，就将两点加入集合中(即将边加入集合)
*/



struct Edge{
	int a,b,w;
	
	bool operator < (const Edge &W)const{
		return w < W.w;
	}
}edges[M];

int n ,m;
int p[N]; // 并查集

// 并查集find函数
int find(int u){
	if(p[u] != u) p[u] = find(p[u]);
	return p[u];
}

int main(){
	cin >> n >> m;
	//
	for(int i = 0 ; i< m; i ++){
		int a,b,c;
		cin >> a >> b >> c;
		edges[i] = {a,b,c};
	}
	// 对边进行升序排序
	sort(edges,edges + m);
	for(int i = 1; i <= n;i ++) p[i] = i; // 初始化并查集
	for(int i = 0; i < m;i ++) // 从小到大枚举所有边
	{
		int a = edges[i].a,b = edges[i].b,w = edges[i].w;
		a = find(a),b = find(b); // 当前边的两点的祖宗节点
		// 如果不在一个集合中就将两点加入一个集合(将边加入集合)
		if(a != b )
		{
			p[a] = b;
			cnt++;
		}
	}
	
	if(cnt < n - 1) // 如果集合中的边数小于n-1条就说明图不连通，求不出最小生成树
}