algorithm - 树中所有边不相交路径的列表

Question

在由具有父子指针的公共(public)节点结构表示的通用树中，如何找到彼此没有重叠边并以叶节点终止的所有路径的列表。

例如，给定这样一棵树:

          1
      /   |   \               
     2    3    4
    / \   |   / \
   5   6  7  8   9 

所需的输出将是如下路径列表:

1    2    1    1    4
|    |    |    |    |
2    6    3    4    9
|         |    | 
5         7    8

或者列表形式:

[[1, 2, 5], [2, 6], [1, 3, 7], [1, 4, 8], [4, 9]]

显然，路径列出了它们自己，它们的顺序可以根据 Twig 的处理顺序而变化。例如，如果我们先处理左分支，下面是另一种可能的解决方案:

[[1, 4, 9], [4, 8], [1, 3, 7], [1, 2, 6], [2, 5]]

对于这个问题，不需要特定的顺序。

Answer 1

您可以使用 recursive DFS algorithm有一些修改。
你没有说你使用什么语言，所以，我希望 C# 适合你。

让我们为树节点定义一个类:

public class Node
{
    public int Id;
    public bool UsedOnce = false;
    public bool Visited = false;
    public Node[] Children;
}

看看 UsedOnce 变量 - 它看起来很不明确。
如果此节点已在输出中使用一次，则 UsedOnce 等于 true。由于我们有一棵树，这也意味着 从该节点到其父节点的一条边 已在输出中使用过一次(在一棵树中，每个节点只有一条父边，即到其父节点的边 parent )。请仔细阅读此内容，以免日后感到困惑。

这里我们有一个简单的、基本的深度优先搜索算法实现。
所有的魔法都将包含在输出方法中。

List<Node> currentPath = new List<Node>(); // list of visited nodes

public void DFS(Node node)
{
    if (node.Children.Length == 0) // if it is a leaf (no children) - output
    {
        OutputAndMarkAsUsedOnce(); // Here goes the magic...
        return;
    }

    foreach (var child in node.Children)
    {
        if (!child.Visited) // for every not visited children call DFS
        {
            child.Visited = true;
            currentPath.Add(child);
            DFS(child); 
            currentPath.Remove(child);
            child.Visited = false;
        }
    }
}

如果 OutputAndMarkedAsUsedOnce 只是输出一个 currentPath 内容，那么我们将有一个像这样的普通 DFS 输出:

1 2 5
1 2 6
1 3 7
1 4 8
1 4 9

现在，我们需要使用我们的UsedOnce。让我们在当前路径中找到最后一个使用过一次的节点(它已经在输出中)并输出包含该节点的所有路径。保证这样的节点存在，因为至少路径中的最后一个节点之前从未遇到过并且不能被标记为使用过一次。

例如，如果当前路径是“1 2 3 4 5”并且 1、2、3 被标记为使用过一次 - 那么输出“3 4 5”。

在你的例子中:

1. 我们在“1 2 5”。全部未使用，输出“1 2 5”，标记1,2,5为已使用一次
2. 现在，我们处于“1 2 6”。使用 1、2 - 2 是最后一个。 2 的输出，包括“2 6”，将 2 和 6 标记为已使用。
3. 现在我们在“1 3 7”，使用 1，唯一和最后一个。从 1 开始输出，包括“1 3 7”。将 1、3、7 标记为已使用。
4. 现在我们在“1 4 8”。 1 被使用，唯一的和最后的。输出“1 4 8”。
5. 现在我们处于“1 4 9”。使用 1、4 个。从 4 输出 - “4 9”。

之所以有效，是因为在树中“使用过的节点”意味着“使用过它与其父节点之间的(唯一父节点)边”。所以，我们实际上标记了使用过的边，并且不再输出它们。

例如，当我们将 2、5 标记为已使用时 - 这意味着我们标记边 1-2 和 2-5。然后，当我们寻找“1 2 6”时——我们不输出边“1-2”，因为它被使用了，而是输出“2-6”。
将根节点(节点 1)标记为已使用一次不会影响输出，因为它的值从未被检查过。它有一个物理解释——根节点没有父边。

抱歉解释不当。不画图很难解释树上的算法 :) 请随时提出有关算法或 C# 的任何问题。

这是工作 IDEOne demo .

P.S. 这段代码可能不是很好且正确的 C# 代码(避免了自动属性，避免了 LINQ)以便其他编码人员可以理解它。

当然，这个算法并不完美——我们可以删除currentPath，因为在树中路径很容易恢复；我们可以提高产量；我们可以将这个算法封装在一个类中。我只是试图展示常见的解决方案。