本文主要是介绍请将图转换成以某个结点为根结点的树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目要求：请将图转换为以某个结点为根结点的数。然后，输出所有从根结点到叶子结点的路径。
例如：
示例输入，
6
0 1
1 2
1 4
3 4
4 5
期望输出，
1 0
1 2
1 4 3
1 4 5
解题思路1：创建一个全局布尔型数组st，访问过的结点不再访问，记得恢复现场。C++代码如下，
#include <iostream>
#include <vector>using namespace std;int n;
vector<vector<int>> g;
vector<int> path;
vector<bool> st;void dfs(int node) {path.emplace_back(node);st[node] = true;bool has_succ = false;for (auto nextnode : g[node]) {if (st[nextnode] == false) {has_succ = true;break;}}if (has_succ == false) {//叶子结点for (auto node : path) {cout << node << " ";}cout << endl;} else {for (auto nextnode : g[node]) {if (st[nextnode] == false) {dfs(nextnode); //进一步递归}}}path.pop_back();st[node] = false;return;
}int main() {cin >> n;g.resize(n);st.resize(n, false);int a, b;while (cin >> a >> b) {g[a].emplace_back(b);g[b].emplace_back(a);}//输出以1号结点为根节点到所有叶子结点的路径dfs(1);return 0;
}
解题思路2（推荐）：深搜时传入当前结点和其父节点。C++代码如下，
#include <iostream>
#include <vector>using namespace std;int n;
vector<vector<int>> g;
vector<int> path;void dfs(int node, int fa) {path.emplace_back(node);bool has_succ = false;for (auto nextnode : g[node]) {if (nextnode != fa) {has_succ = true;break;}}if (has_succ == false) {//叶子结点for (auto node : path) {cout << node << " ";}cout << endl;} else {for (auto nextnode : g[node]) {if (nextnode != fa) {dfs(nextnode, node); //进一步递归}}}path.pop_back();return;
}int main() {cin >> n;g.resize(n);int a, b;while (cin >> a >> b) {g[a].emplace_back(b);g[b].emplace_back(a);}//输出以1号结点为根节点到所有叶子结点的路径dfs(1, -1);return 0;
}
这篇关于请将图转换成以某个结点为根结点的树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
