有根树的遍历
考察树的思想和dfs、bfs的实现,做不出来说明 dfs、bfs没有掌握 且 树的思想没有领悟。
//有根树的遍历 #include <bits/stdc++.h> using namespace std; vector<int> to[200005]; int n, a, vis[200005], q[200005]; int cmp(int b, int c) { return b > c; } void ad(int u, int v) { to[u].push_back(v); } void dfs(int k) { cout << k << ' '; for (int i = 0; i < to[k].size(); i++) { if (vis[to[k][i]] == 0) { vis[to[k][i]] = 1; dfs(to[k][i]); } } } void bfs(int k) { int head = 1, tail = 1; q[tail++] = k;while (head < tail) { int now = q[head++]; cout << now << " ";for (int i = 0; i < to[now].size(); i++) { if (vis[to[now][i]] == 0) { vis[to[now][i]] = 1; q[tail++] = to[now][i]; } } } } int main() { cin >> n; for (int i = 1; i <= n - 1; i++) { cin >> a; ad(a, i); ad(i, a); } for (int i = 0; i < n; i++) sort(to[i].begin(), to[i].end(), cmp); vis[0] = 1; dfs(0); memset(vis, 0, sizeof(vis)); cout << endl; vis[0] = 1; bfs(0); return 0; }
无根树的遍历
这个题和上一个有什么区别?没区别 =.=
#include <bits/stdc++.h> using namespace std; vector<int> to[200005]; int n, a, vis[200005], q[200005], start; int cmp(int b, int c) { return b > c; } void ad(int u, int v) { to[u].push_back(v); } void dfs(int k) { cout << k << ' '; for (int i = 0; i < to[k].size(); i++) { if (vis[to[k][i]] == 0) { vis[to[k][i]] = 1; dfs(to[k][i]); } } } void bfs(int k) { int head = 1, tail = 1; q[tail++] = k; while (head < tail) { int now = q[head++]; cout << now << " "; for (int i = 0; i < to[now].size(); i++) { if (vis[to[now][i]] == 0) { vis[to[now][i]] = 1; q[tail++] = to[now][i]; } } } } int main() { cin >> n; for (int i = 1; i <= n - 1; i++) { cin >> a; ad(a, i); ad(i, a); } cin >> start; for (int i = 0; i < n; i++) sort(to[i].begin(), to[i].end(), cmp); vis[start] = 1; dfs(start); memset(vis, 0, sizeof(vis)); cout << endl; vis[start] = 1; bfs(start); return 0; }
View Code
原文链接: https://www.cnblogs.com/phemiku/p/11426569.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/301694
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!