修改教材2.2节例2.9的程序,使其能输出图中所有路径(path)。
时间: 2024-03-10 15:50:15 浏览: 30
好的,我可以为您修改该程序。原来的程序是:
```
void dfs(int u) {
if (u == t) {
printf("%d ", u);
return;
}
st[u] = true;
for (int i = h[u]; i != -1; i = e[i].ne) {
int j = e[i].to;
if (!st[j]) dfs(j);
}
}
```
修改后的程序如下所示,使用一个vector来存储路径,每次遍历到目标节点时,将路径存入结果中,并回溯删除该路径上的节点。
```
void dfs(int u, vector<int>& path, vector<vector<int>>& res) {
path.push_back(u);
if (u == t) {
res.push_back(path);
path.pop_back();
return;
}
st[u] = true;
for (int i = h[u]; i != -1; i = e[i].ne) {
int j = e[i].to;
if (!st[j]) dfs(j, path, res);
}
path.pop_back();
}
```
调用方式为:
```
vector<int> path;
vector<vector<int>> res;
dfs(s, path, res);
for (auto& p : res) {
for (auto& x : p) printf("%d ", x);
printf("\n");
}
```
这样,程序就能输出图中所有路径(path)了。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)