当前位置： 首页 > article >正文

搜索与图论算法总结

article 2024/9/20 23:25:07

图论总结

搜索

DFS

dfs可以说是选择一条可行的路径一直走到头，到头之后就是往回走，往回走也有一定的程度，比如往回走了一步，发现又可以往下走了，就继续走。dfs函数写在什么位置，可以这么理解，等于dfs()是一条分界线，他的上边的逻辑我要做什么，修改标志之类的，他的下边就是我做上边的那些没有成功，就要恢复现场

排列数字

#include<iostream>
using namespace std;
const int N=11;
int path[N];
bool st[N];
int n;

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        puts("");
    }
    
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    }
}

int main(){
    scanf("%d",&n);
    dfs(0);
}

n皇后问题

#include<iostream>
using namespace std;
const int N=11,M=22;
char q[N][N];
bool col[M],dg[M],udg[M];
int n;

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) puts(q[i]);
        puts("");
    }
    
    for(int i=0;i<n;i++){
        if(!col[i] && !dg[u+i] && !udg[u+n-i]){
            q[u][i]='Q';
            col[i]=dg[u+i]=udg[u+n-i]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[u+n-i]=false;
            q[u][i]='.';
        }
    }
}

int main(){
    scanf("%d",&n);
    
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            q[i][j]='.';
    dfs(0);
}
BFS

BFS就是一层一层往下走，如果符合条件就把他装入队列中，并且维护一些东西，然后每次也是取队头元素进行下一步操作

走迷宫(经典例题)

#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int g[N][N],d[N][N];
int n,m;
PII q[N*N];

void bfs(){
    int hh=0,tt=-1;
    memset(d,-1,sizeof d);
    d[0][0]=0;
    q[++tt] = {0,0};
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(hh<=tt){
        PII t=q[hh++];
        for(int i=0;i<4;i++){
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x>=0 && x<n && y>=0 && y<m && !g[x][y] && d[x][y]==-1){
                d[x][y]=d[t.first][t.second]+1;
                q[++tt] = {x,y};
            }
        }
    }
    printf("%d",d[n-1][m-1]);
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            scanf("%d",&g[i][j]);
    }
    bfs();
}
树与图的深度优先遍历
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N*2],ne[N*2],idx;
bool st[N];
int n;
int ans = N;

void add(int a,int b){
    e[idx] = b;
    ne[idx]=h[a];
    h[a]=idx++;
} 

int dfs(int u){
    st[u]=true;
    int sum=1,res=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            int s=dfs(j);
            sum += s;
            res=max(res,s);
        }
    }
    res=max(res,n-sum);
    ans=min(res,ans);
    return sum;
}

int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1);
    printf("%d",ans);
}
树与图的广度优先遍历
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void bfs(){
    int hh=0,tt=-1;
    q[++tt] = 1;
    memset(d,-1,sizeof d);
    d[1]=0;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]==-1){
                d[j]=d[t]+1;
                q[++tt] = j;
            }
        }
    }
    printf("%d",d[n]);
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    bfs();
}
有向图的拓扑序列
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N];
int n,m;
int q[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!d[i]) q[++tt] = i;
    }
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(--d[j]==0){
                q[++tt] = j;
            }
        }
    }
    return tt==n-1;
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    if(topsort()){
        for(int i=0;i<n;i++) printf("%d ",q[i]);
    }
    else puts("-1");
}
Dijkstra算法求解最短路问题
#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t=j;
        }
         for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        st[t]=true;
    }
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    if(t==0x3f3f3f3f) puts("-1");
    else printf("%d",t);
}
Dijkstra算法求解最短路问题(小根堆优化)

主要是通过小根堆优化每次找最小值的过程

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010,M=200010;
typedef pair<int,int> PII;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int n,m;

void add(int a,int b,int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    while(heap.size()){
        PII t=heap.top();
        heap.pop();
        int ver=t.second;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=dijkstra();
    if(t==0x3f3f3f3f) puts("-1");
    else printf("%d",t);
}
bellman-ford算法求解有负边的最短路
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],last[N];
struct Edge{
	int a,b,c;
}edges[M];

int bellman_ford(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=0;i<k;i++){
		memcpy(last,dist,sizeof dist);
		for(int j=0;j<m;j++){
			Edge e=edges[j];
			dist[e.b]=min(dist[e.b],last[e.a]+e.c);
		}
	}
	return dist[n];
}


int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		edges[i]={a,b,c};
	}
	int t=bellman_ford();
	if(t>0x3f3f3f3f/2) puts("impossible");
	else printf("%d",t);
}
spfa算法

spfa求解最短路

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
int dist[N],q[N];
bool st[N];
int n,m;

void add(int a,int b,int c){
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}

int spfa(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	int hh=0,tt=-1;
	q[++tt] = 1;
	while(hh<=tt){
		int t=q[hh++];
		st[t]=false;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[t]+w[i]){
			    dist[j]=dist[t]+w[i];
			    if(!st[j]){
    				st[j]=true;
    				q[++tt] = j;
    			}
			}
			
		}
	}
	return dist[n];
}

int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	int t=spfa();
	if(t==0x3f3f3f3f) puts("impossible");
	else printf("%d",t);
}

spfa求负环

#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=10010;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],q[N*M],cnt[N];
bool st[N];
int n,m;

void add(int a,int b,int c){
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++;
}

bool spfa(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	int hh=0,tt=-1;
	for(int i=1;i<=n;i++){
		q[++tt] = i;
	}
	while(hh<=tt){
		int t=q[hh++];
		st[t]=false;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[t]+w[i]){
				dist[j]=dist[t]+w[i];
				cnt[j]=cnt[t]+1;
				if(cnt[j]>=n) return true;
				if(!st[j]){
					st[j]=true;
					q[++tt] = j;
				}
			}
		}
	}
	return false;
}

int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	
	if(spfa()) puts("Yes");
	else puts("No");
}
floyd求解多源最短路
#include<iostream>
using namespace std;
const int N=210,INF=1e9;
int d[N][N];
int n,m,q;

void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) d[i][j]=0;
			else d[i][j]=INF;
		}
	}
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		d[a][b]=min(d[a][b],c);
	}
	floyd();
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		if(d[a][b]> INF/2 ) puts("impossible");
		else printf("%d\n",d[a][b]);
	}
}
prim算法求解最短生成树
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m;

int prim(){
	memset(dist,0x3f,sizeof dist);
	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[t]>dist[j]))
				t=j;
		}
		if(i && dist[t]==INF) return INF;
		if(i) res += dist[t];
		for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
		st[t]=true;
	}
	return res;
}

int main(){
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof g);
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	int t=prim();
	if(t==INF) puts("impossible");
	else printf("%d",t);
}
kruskal算法求解最小生成树

kruskal算法其中就有一些并查集的思想，把边从权值小的往大的找，当连通了之后就停止，也就是他们的父节点相同。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=200010,INF=0x3f3f3f3f;
int p[N];
struct Edge{
	int a,b,w;
}edges[M];
int res,cnt;
int n,m;

bool cmp(struct Edge a,struct Edge b){
	return a.w<b.w;
}

int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

int kruskal(){
	sort(edges,edges+m,cmp);
	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;
			res += w;
			cnt++;
		}
	}
	return cnt<n-1 ? INF : res;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		edges[i]={a,b,c};
	}
	
	for(int i=1;i<=n;i++) p[i]=i;
	
	int t=kruskal();
	if(t==INF) puts("impossible");
	else printf("%d",t);
}
染色法判定二分图

**总体思想：**二分图就是分成两边，然后一边染一个色，如果最后的出现重复染色的情况（即染色冲突），就不是二分图

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
void add(int a,int b){
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++;
}

bool dfs(int u,int c){
	color[u]=c;
	for(int i=h[u];i!=-1;i=ne[i]){
		int j=e[i];
		if(!color[j]){
			if(!dfs(j,3-c)) return false;
		}else if(color[j]==c) return false;
	}
	return true;
}

int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	bool flag=true;
	for(int i=1;i<=n;i++){
		if(!color[i]){
			if(!dfs(i,1)){
				flag=false;
				break;
			}
		}
		
	}
	if(flag) puts("Yes");
	else puts("No");
}
匈牙利算法求解二分图最大匹配
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
bool st[N];
int n1,n2,m;
int match[N];

void add(int a,int b){
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++;
}

bool find(int u){
	for(int i=h[u];i!=-1;i=ne[i]){
		int j=e[i];
		if(!st[j]){
			st[j]=true;
			if(!match[j] || find(match[j])){
				match[j]=u;
				return true;
			}
		}
	}
	return false;
}

int main(){
	scanf("%d%d%d",&n1,&n2,&m);
	memset(h,-1,sizeof h);
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	int res=0;
	for(int i=1;i<=n1;i++){
		memset(st,false,sizeof st);
		if(find(i)) res++;
	}
	
	printf("%d",res);
}

http://www.kler.cn/news/149931.html

相关文章：

  • 基于C#实现优先队列
  • Ubuntu上的常用软件配置
  • 人工智能与供应链行业融合：预测算法的通用化与实战化
  • 如何使用ArcGIS Pro制作一张北极俯视地图
  • 初识向量数据库
  • yolov4、yolov5优化策略
  • Vue基本使用(一)
  • [Docker]九.Docker compose讲解
  • AIGC:文本生成视频
  • 【笔记】windows+pytorch：部署一下stable diffusion和NeRF
  • C++ day44完全背包问题 零钱兑换Ⅱ 组合总和Ⅳ
  • C语言基础--#if与#endif
  • 深入了解Spring Boot中@Async注解的8大坑点
  • ISCTF2023 部分wp
  • 网络安全 | 使用人工智能阻止网络攻击
  • 微服务实战系列之Redis（cache）
  • 行情分析——加密货币市场大盘走势(11.29)
  • 七、Lua字符串
  • 工艺系统所管理数字化实践
  • spark-submit
  • 靡靡之音 天籁之声 ——Adobe Audition
  • stm32 计数模式
  • Django路由分发
  • 荣耀IPO站上新起点：市场望眼欲穿，发展未来可期
  • Redis-Day1基础篇(初识Redis, Redis常见命令, Redis的Java客户端)
  • Sass基础知识之【变量】
  • 【送书活动二期】Java和MySQL数据库中关于小数的保存问题
  • Fuzz进阶教学——人工智能在模糊测试中的应用
  • Linux使用宝塔面板+Discuz+cpolar内网穿透工具搭建可公网访问论坛
  • nodejs669在线图书借阅管理系统vue前端