c++数据结构第六周图，深搜、广搜stl版

本方法皆用vector进行邻接表模拟

7-1 图的先深搜索
作者 唐艳琴
单位 中国人民解放军陆军工程大学

输出无向图的给定起点的先深序列。
输入格式:

输入第一行给出三个正整数，分别表示无向图的节点数N（1<N≤10）、边数M（≤50）和探索起始节点编号S（节点从1到N编号）。

随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号。
输出格式:

输出从S开始的无向图的先深搜索序列，用一个空格隔开，最后也有一个空格；如果为非连通图，再在结尾处另起一行输出一个0，表示此图非连通。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以表头插入法构造邻接表。
输入样例1:

6 8 2
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

输出样例1:

2 3 6 4 5 1

输入样例2:

4 3 1
1 2
2 3
3 1

输出样例1:

1 3 2
0

#include<bits/stdc  .h>
using namespace std;
int n,m,s,a,b,cnt;
vector<int>road[15];
bool check[15];
void dfs(int now){
	check[now]=true;
	cout<<now<<" ";
	cnt  ;
	for(int i=road[now].size()-1;i>=0;--i){
		if(!check[road[now][i]]){
			dfs(road[now][i]);
		}
	}
}
int main(){
	cin>>n>>m>>s;
	while(m--){
		cin>>a>>b;
		road[a].push_back(b);
		road[b].push_back(a);
	}
	dfs(s);
	cout<<(cnt==n?"":"\n0");
}

7-2 图的先广搜索
作者 唐艳琴
单位 中国人民解放军陆军工程大学

输出无向图的给定起点的先广序列。
输入格式:

输入第一行给出三个正整数，分别表示无向图的节点数N（1<N≤10）、边数M（≤50）和探索起始节点编号S（节点从1到N编号）。

随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号。
输出格式:

输出从S开始的无向图的先广搜索序列，用一个空格隔开，最后也有一个空格；如果为非连通图，再在结尾处另起一行输出一个0，表示此图非连通。

由于广度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以表头插入法构造邻接表。
输入样例:

6 8 2
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

输出样例:

2 3 1 6 4 5

#include<bits/stdc  .h>
using namespace std;
int n,m,s,a,b,cnt;
vector<int>road[15];
bool check[15];
queue<int>q;
void bfs(int begin){
	q.push(begin);
	while(!q.empty()){
		begin=q.front();q.pop();
		if(check[begin]) continue;
		cout<<begin<<" ";check[begin]=true;cnt  ;
		for(int i=road[begin].size()-1;i>=0;--i){
			q.push(road[begin][i]);
		}
	}
}
int main(){
	cin>>n>>m>>s;
	while(m--){
		cin>>a>>b;
		road[a].push_back(b);
		road[b].push_back(a);
	}
	bfs(s);
	cout<<(cnt==n?"":"\n0");
}

这篇好文章是转载于：学新通技术网