树递归 - 如何在深度优先搜索中包含条件？

Question

我有一棵树（非二进制、不平衡、无循环），所有节点都有标志（绿色=活动，红色=不活动）。我从根节点开始，我必须找到所有节点都处于活动状态的完整路径（从根到叶）。（至少找到一条路径就可以了。）因此，我需要路径，而不仅仅是信息（如果有的话）。

我正在考虑使用深度优先搜索，但我不知道如何包含 active/inactive 的过滤。有什么想法吗？

Answer 1

很简单。大家知道，DFS可以用栈来实现。这样我们就将树的根压入栈中，然后弹出栈顶并压入弹出节点的子节点。我们继续这个过程直到有一个空堆栈。

现在，对于您的情况，就在将节点压入堆栈之前，您需要检查指定节点（即弹出节点的子节点）是活动的还是非活动的。在这种情况下，您将不会在到达非活动节点时向下搜索。最后，只报告所有生成的路径，其结束节点是叶子（您可以在搜索时轻松找到叶子，一个没有任何子节点的节点）。

Answer 2

您的 DFS 递归将有两个基本情况：

负一：当前节点不是绿色
正数：当前节点是一片绿叶，即没有子节点。

在所有其他情况下，必须对节点的子节点进行递归调用。一旦递归调用返回肯定结果，就可以使用当前节点扩展该肯定结果并立即返回，从而中断循环。

有几种实现树的方法，所以我在这个JavaScript实现中做了一些选择：

function findGreenPath(tree, label) {
    let root = tree[label];
    if (!root.green) return null; // No path through none-green node
    if (root.children == "") return label; // It is a leaf, start a path
    for (let child of root.children) {
        let path = findGreenPath(tree, child);
        if (path != null) return label + path; // prepend this node to a good path
    }
    return null; // No path found
}

// Implementation of the example tree in the question:
let tree = { // Dictionary of nodes by their label
    "A": {green: true, children: "BC"},
    "B": {green: true, children: "DE"},
    "C": {green: true, children: "FG"},
    "D": {green: true, children: "HI"},
    "E": {green: false, children: ""},
    "F": {green: false, children: ""},
    "G": {green: true, children: "J"},
    "H": {green: false, children: ""},
    "I": {green: true, children: ""},
    "J": {green: true, children: "K"},
    "K": {green: false, children: ""}
};

let path = findGreenPath(tree, "A"); 

console.log(path); // ABDI

Answer 3

假设

        A                              1
       / \                            / \
      B   C -- G                     2   3 -- 7
     / \   \    \        <=>        / \   \    \
    D   E   F    J                 4   5   6    10
   / \            \               / \            \
  H   I            K             8   9            11

因此，我可以使用算法 深度优先搜索.

提供您问题的解决方案

/*
A - 1,
B - 2,
C - 3,
D - 4,
E - 5,
F - 6,
G - 7,
H - 8,
I - 9,
J - 10,
K - 11.
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int maximumSize=20;
int vertices, edges;
vector<int> visited0(maximumSize, 0);
vector<int> visited1(maximumSize, 0);
vector<int> graph[maximumSize];
vector<int> distances(maximumSize, 0);
vector<string> graphPaths;
string path;
vector<int> green(maximumSize, 0);
template<class Type>
void showContent1D(Type& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
void showContentVectorString(vector<string>& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int i=1; i<=edges; ++i)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    for(int i=1; i<=vertices; ++i)
    {
        cin>>green[i];
    }
    return;
}
void dfs0(int current, int previous)
{
    if(visited0[current]==1)
    {
        return;
    }
    visited0[current]=1;
    distances[current]=0;
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        dfs0(next, current);
        distances[current]=max(distances[current], distances[next]+1);
    }
    return;
}
void dfs1(int root, int current, int previous)
{
    if(visited1[current]==1)
    {
        return;
    }
    visited1[current]=1;
    if(green[current]==1)
    {
        if(distances[current]!=0)
        {
            path.append(to_string(current));
            path.append("->");
        }
        else
        {
            path.append(to_string(current));
            graphPaths.push_back(path);
            path.pop_back();
        }
    }
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        dfs1(root, next, current);
    }
    if(root==previous)
    {
        path.clear();
        path.append(to_string(root));
        path.append("->");
    }
    return;
}
void solve()
{
    createGraph();
    dfs0(1, 0);
    dfs1(1, 1, 0);
    cout<<"graphPaths: ";
    showContentVectorString(graphPaths);
    cout<<endl;
    return;
}
int main()
{
    solve();
    return 0;
}

输入：

结果如下：

graphPaths: 1->2->4->9,

如果您需要解决方案的解释，请写下相应的评论。

树递归 - 如何在深度优先搜索中包含条件？

Tree recursion - how to include conditions in depth-first search?

algorithm

tree

recursion

depth-first-search