c++ - C++ 中的“扩展”深度优先搜索
问题描述
我知道如何在 C++ 中实现深度优先搜索算法,但我需要一个“扩展版本”。所以,我有一张地图
map<int, map<int,int> > tree;
对于任何顶点,它返回一个以相邻顶点作为键和(对我的程序很重要)边缘索引作为值的映射。树的根是第一个 (1) 顶点。所以,这是我的代码:
stack<int> s;
for(const auto &pair : tree[1]) s.push(pair.first);
while(!s.empty()) {
if(!visited[s.top()]) { //it's just bool array
roads[s.top()] = {0}; // ???
for(const auto &pair : tree[s.top()]) s.push(pair.first);
}
s.pop();
}
我需要做的是创建一个向量向量,其中对于每个顶点,我将有一个完整的路径(表示为边缘索引)。
例如像这样的图表:
1
/ \
(i=2)/ \(i=1)
/ \
2 3
/\
/ \
(i=3)/ \(i=4)
/ \
4 5
我想要这样的东西:
vector< vector<int> > roads = {{},{},{2},{1},{1,3},{1,4};
因为roads[0]
也不存在,roads[1]
并且对于其他每个我们都有表示为边缘索引的路径。
编辑
换句话说,我想做的是:对于给定树中的每个顶点,我想知道从根到该顶点的路径。这棵树中的每条边都有自己的编号,因此路径将表示为向量或集合(为简单起见,我根本不关心边的顺序)。
解决方案
“无环图”也称为树。
您想要一个包含所有边标签序列的列表,这些边标签代表从根到某个顶点的路径?
遍历的伪代码(我想这将有资格作为preorder
遍历):
void collect(node, //current node
labels, //labels of edges leading to node
&paths //all the paths collected so far, writeable, contains results
) {
paths.add(labels);
foreach ((neighbor_node, edge_name) in (unvisited neighbors of node)) {
labels.add(edge_name);
collect(neighbor_node, labels, paths);
labels.remove(edge_name);
}
}
start with collect(root, empty_list, empty_list);
推荐阅读
- python - 没有预期输出的Python字符串替换
- java - 通过单击位于 PopUpWindow (Android Studio) 上的按钮打开活动
- c++ - 使用 MSVC 编译器和 GCC 编译器时得到不同的结果。如何在 msvc(visual studio) 中获得与 gcc 相同的输出?
- julia - 更改 Julia 中的结构字段值数组
- r - 如何在 R 中导入 .txt 文件以供读取?
- tablesorter - 用于排序和过滤的不同文本
- c# - 如何使用 MailMessage 使用 SendGrid 发送邮件?
- wordpress - 删除自动
来自 Wordpress 中的高级自定义字段的标签,但保留
标签 - python - 找不到页面 (404) 请求方法:POST 请求 URL:http://127.0.0.1:8000/signup/signup/
- python - Python如何在单元测试中隐藏回溯