台州网站优化方案,动态asp.net网站开发教程,专注专业网站建设,怎么设立网站题目描述
给定一棵大小为 n n n#xff0c;根为 1 1 1 的树#xff0c;求出其按照 dfs 和 bfs 进行遍历时的顺序。
请将所有出点按照编号从小到大排序后进行遍历。
dfs 为深度优先搜索#xff0c;bfs 为宽度优先搜索。
输入格式
一个整数 n n n#xff0c;表示点的…题目描述
给定一棵大小为 n n n根为 1 1 1 的树求出其按照 dfs 和 bfs 进行遍历时的顺序。
请将所有出点按照编号从小到大排序后进行遍历。
dfs 为深度优先搜索bfs 为宽度优先搜索。
输入格式
一个整数 n n n表示点的个数。 ( 1 ≤ n ≤ 50 ) (1 \leq n \leq 50) (1≤n≤50)
接下来一行 n − 1 n-1 n−1 个整数表示点 2 ∼ n 2 \sim n 2∼n 的父亲 f a i fa_i fai。 ( 1 ≤ f a i ≤ n ) (1 \leq fa_i \leq n) (1≤fai≤n)
输出格式
第一行输出 dfs 时的顺序第二行输出 bfs 时的顺序。
样例输入1
4
1 1 2样例输出1
1 2 4 3
1 2 3 4样例输入2
5
1 2 2 4样例输出2
1 2 3 4 5
1 2 3 4 5思路
数组 fa 来存储每个节点的父节点向量数组 edges 来存储图的边。
在 main 函数中首先读取节点的数量 n然后读取每个节点的父节点将每个节点添加到其父节点的边列表中。接着对每个节点的边列表进行排序以保证遍历的顺序。
调用 dfs 函数进行深度优先搜索。在 dfs 函数中首先将起始节点压入栈 s1然后在栈不为空的情况下弹出栈顶元素打印其值然后将其所有子节点除去父节点压入栈 s2。接着将 s2 中的所有节点都压入 s1这样就实现了深度优先的遍历顺序。
调用 bfs 函数进行广度优先搜索。在 bfs 函数中首先将起始节点加入队列 q1然后在队列不为空的情况下弹出队首元素打印其值然后将其所有子节点除去父节点加入队列。这样就实现了广度优先的遍历顺序。 AC代码
#include algorithm
#include iostream
#include queue
#include stack
#include vector
#define AUTHOR HEX9CF
using namespace std;const int N 1e3 7;int n;
int fa[N];
vectorint edges[N];void dfs(int x) {stackint s1;stackint s2;s1.push(x);while (s1.size()) {int t s1.top();s1.pop();cout t ;for (auto i : edges[t]) {if (i fa[t]) {continue;}s2.push(i);}while (s2.size()) {s1.push(s2.top());s2.pop();}}
}void bfs(int x) {queueint q1;q1.push(x);while (q1.size()) {int f q1.front();q1.pop();cout f ;for (auto i : edges[f]) {if (i fa[f]) {continue;}q1.push(i);}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for (int i 2; i n; i) {cin fa[i];edges[fa[i]].push_back(i);}for (int i 1; i n; i) {sort(edges[i].begin(), edges[i].end());}dfs(1);cout endl;bfs(1);cout endl;return 0;
}
