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");
}