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");
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfckch
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01