"Extended" C++ 中的深度优先搜索

Question

我知道如何用C++实现深度优先搜索算法，但我需要一个“扩展版”。所以，我有一张地图

map<int, map<int,int> > tree;

对于任何顶点，它 returns 一个以相邻顶点作为键和（对我的程序很重要）边索引作为值的映射。树的根是第一个 (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] 也不存在，并且对于每一个我们都有表示为边缘索引的路径。

编辑

换句话说我想做的是：对于给定树中的每个顶点，我想知道从根到该顶点的路径。这棵树中的每条边都有自己的编号，因此路径可以表示为向量或集合（为了简单起见，我根本不关心边的顺序）。

Answer 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);

"Extended" C++ 中的深度优先搜索

"Extended" depth-first search in C++

c++

algorithm

depth-first-search

shortest-path