广度优先搜索算法的思想：以v作为源点出发访问其他节点，首先使用队列存储节点，再从队列中取出节点，遍历查找v和其他连通的节点，将和v连通的节点并且未被访问过的节点入队，遍历完和v连通的节点；再从队列中取出一个节点w，并以此节点为源点出发遍历和该源点连通的点并且是未被访问过的点入队，如此的重复下去，直到所有的点都被访问过。注意广度优先搜索是先访问和自身节点连通的节点，所以用队列来存储。`
一：有向图
在这里插入图片描述

方法一：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxx=105;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];//记录节点之间的是否连通
int ans[maxx];//记录访问顺序
int n,m;
int vis[maxx];//记录访问情况
queue<int>q;//队列存储节点
int index;
void bfs(int n,int s){
	vis[s]=1;
	ans[index++]=s;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=1;i<=n;i++){
			if(e[u][i]==1){
				if(vis[i]==0){
					q.push(i);
					ans[index++]=i;
					vis[i]=1;
				}
			}
		}
	}
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	memset(vis,0,sizeof(vis));
    	memset(e,0,sizeof(e));
    	memset(ans,0,sizeof(ans));
    	index=1;
    	for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d %d",&a,&b);
    		e[a][b]=1;
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				bfs(n,i);
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}	
	return 0;
}
/*
7 8
1 2
2 5
1 3
3 4
4 5
4 2
1 4
6 7
*/

方法二：邻接表
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxx=105;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];
int ans[maxx];
int n,m;
int vis[maxx];
queue<int>q;
int index;
vector<int>G[maxx];
void bfs(int n,int s){
	vis[s]=1;
	ans[index++]=s;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			if(vis[v]==0){
				q.push(v);
				ans[index++]=v;
				vis[v]=1;
			}
		}
	}
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	memset(vis,0,sizeof(vis));
    	memset(e,0,sizeof(e));
    	memset(ans,0,sizeof(ans));
    	index=1;
    	for(int i=1;i<=n;i++){
    		G[i].clear();
		}
    	for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d %d",&a,&b);
    		G[a].push_back(b);
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				bfs(n,i);
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}	
	return 0;
}
/*
7 8
1 2
2 5
1 3
3 4
4 5
4 2
1 4
6 7
*/

在这里插入图片描述

方法三：链式前向星
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxx=105;
const int inf=0x3f3f3f3f;
int head[maxx];
int ans[maxx];
int n,m;
int vis[maxx];
queue<int>q;
int index;
struct node{
	int u,v;
	int next;
}e[maxx];
int cnt;
void add(int u,int v){
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
void bfs(int n,int s){
	vis[s]=1;
	ans[index++]=s;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			if(vis[v]==0){
				q.push(v);
				ans[index++]=v;
				vis[v]=1;
			}
		}
	}
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	memset(vis,0,sizeof(vis));
    	memset(ans,0,sizeof(ans));
    	memset(head,-1,sizeof(head));
    	index=1;
    	cnt=0;
    	for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d %d",&a,&b);
    		add(a,b);
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				bfs(n,i);
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}	
	return 0;
}
/*
7 8
1 2
2 5
1 3
3 4
4 5
4 2
1 4
6 7
*/

在这里插入图片描述

二：无向图
在这里插入图片描述

方法一：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxx=105;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];
int ans[maxx];
int n,m;
int vis[maxx];
queue<int>q;
int index;
void bfs(int n,int s){
	vis[s]=1;
	ans[index++]=s;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=1;i<=n;i++){
			if(e[u][i]==1){
				if(vis[i]==0){
					q.push(i);
					ans[index++]=i;
					vis[i]=1;
				}
			}
		}
	}
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	memset(vis,0,sizeof(vis));
    	memset(e,0,sizeof(e));
    	memset(ans,0,sizeof(ans));
    	index=1;
    	for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d %d",&a,&b);
    		e[a][b]=e[b][a]=1;
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				bfs(n,i);
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}	
	return 0;
}
/*
7 8
1 2
2 5
1 3
3 4
4 5
4 2
1 4
6 7
*/

方法二：邻接表
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxx=105;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];
int ans[maxx];
int n,m;
int vis[maxx];
queue<int>q;
int index;
vector<int>G[maxx];
void bfs(int n,int s){
	vis[s]=1;
	ans[index++]=s;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			if(vis[v]==0){
				q.push(v);
				ans[index++]=v;
				vis[v]=1;
			}
		}
	}
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	memset(vis,0,sizeof(vis));
    	memset(e,0,sizeof(e));
    	memset(ans,0,sizeof(ans));
    	index=1;
    	for(int i=1;i<=n;i++){
    		G[i].clear();
		}
    	for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d %d",&a,&b);
    		G[a].push_back(b);
    		G[b].push_back(a);
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				bfs(n,i);
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}	
	return 0;
}
/*
7 8
1 2
2 5
1 3
3 4
4 5
4 2
1 4
6 7
*/

在这里插入图片描述

方法三：链式前向星
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxx=105;
const int inf=0x3f3f3f3f;
int head[maxx];
int ans[maxx];
int n,m;
int vis[maxx];
queue<int>q;
int index;
struct node{
	int u,v;
	int next;
}e[maxx];
int cnt;
void add(int u,int v){
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
void bfs(int n,int s){
	vis[s]=1;
	ans[index++]=s;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			if(vis[v]==0){
				q.push(v);
				ans[index++]=v;
				vis[v]=1;
			}
		}
	}
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
    	memset(vis,0,sizeof(vis));
    	memset(ans,0,sizeof(ans));
    	memset(head,-1,sizeof(head));
    	index=1;
    	cnt=0;
    	for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d %d",&a,&b);
    		add(a,b);
    		add(b,a);
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				bfs(n,i);
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}	
	return 0;
}
/*
7 8
1 2
2 5
1 3
3 4
4 5
4 2
1 4
6 7
*/

在这里插入图片描述

# 数据结构 # 算法
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区