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

Question

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

6

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

例如，给定如下所示的树：

          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]]

显然，路径列表本身及其顺序可以根据树分支处理的顺序而变化。例如，如果我们首先处理左分支，则以下是另一种可能的解决方案：

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

本问题不需要特定的顺序。

- Basel Shishani

你是在寻找正式的、可工作的代码，还是只需要一个算法？ - Tim Biegeleisen

当然，工作代码更好，我通常使用Python而不是伪代码，因为它更容易测试。 - Basel Shishani

提示：添加一个约束条件，使解决方案唯一。 - Colonel Panic

@BaselShishani，由于您没有提到任何编程语言，我写了一个算法。希望它能有所帮助。 - Sumeet

4个回答

2

这是一棵树。其他解决方案可能有效，但过于复杂。在Python中表示树结构。

class Node:
    def __init__(self, label, children):
        self.label = label
        self.children = children

然后树。

请按照以下步骤创建一个递归过程，其中 Node(1, [Node(2, []), Node(3, [Node(4, []), Node(5, [])])]) 是根节点。我们保证根节点出现在第一条路径中。

def disjointpaths(node):
    if node.children:
        paths = []
        for child in node.children:
            childpaths = disjointpaths(child)
            childpaths[0].insert(0, node.label)
            paths.extend(childpaths)
        return paths
    else:
        return [[node.label]]

这可以进行优化（首要目标：停止在列表前插入）。

- David Eisenstat

1

对于所有的顶点，如果该顶点是叶子节点（没有子指针），则沿着父链一直找到一个标记过的顶点或者没有父节点的顶点。标记所有访问过的顶点。将顶点收集到中间列表中，然后反转它并添加到结果中。

如果无法将标记添加到顶点对象本身，则可以将标记实现为已访问顶点的单独集合，并将所有添加到集合中的顶点视为已标记。

- Tagir Valeev

1

使用深度优先搜索（DFS）可以很容易地完成这个任务。

我们从根节点调用DFS。

DFS(root,list)

列表最初包含的内容是

list = {root}

现在算法的步骤如下：

DFS(ptr,list)
{
 if(ptr is a leaf)
  print the list and return
 else
 {
  for ith children of ptr do
  {
   if(ptr is root)
   {
    add the child to list
    DFS(ith child of ptr,list)
    remove the added child
   }
   else if(i equals 1 that is first child)
   {
    add the child to list
    DFS(ith child of ptr,list)
   }
   else
   {
    initialize a new empty list list2
    add ith child and the ptr node to list2
    DFS(ith child of ptr,list2)
   }
  }
 }
}

- Sumeet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yeldar Kurmangaliyev · Accepted Answer

你可以使用一种带有一些修改的递归DFS算法。你没有说你使用的是什么语言，所以我希望C#对你来说没问题。

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

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

看看UsedOnce变量 - 它可能看起来非常模糊。
如果此节点在输出中使用了一次，则UsedOnce等于true。由于我们有一棵树，这也意味着从此节点到其父节点的边缘已在输出中使用了一次（在树中，每个节点只有一条指向其父节点的父边）。仔细阅读以避免在将来混淆。

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

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的输出结果，如下所示：

现在，我们需要使用UsedOnce。让我们在当前路径中找到最后一个已经输出的仅使用一次节点，并从该节点开始输出整个路径，包括它自己。保证这样的节点存在，因为至少路径中的最后一个节点从未遇到过，也不能被标记为仅使用一次。

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

在你的示例中：

我们在 "1 2 5"。它们都未使用，输出 "1 2 5" 并将 1、2、5 标记为已使用一次。
现在，我们在 "1 2 6"。1、2 已被使用 - 2 是最后一个。从 2 开始输出，"2 6"，并将 2 和 6 标记为已使用。
现在我们在 "1 3 7"，1 已被使用，是唯一的且为最后一个。从 1 开始输出，"1 3 7"。将 1、3、7 标记为已使用。
现在我们在 "1 4 8"。1 已被使用，是唯一的且为最后一个。输出 "1 4 8"。
现在我们在 "1 4 9"。1、4 已被使用。从 4 开始输出，"4 9"。

这个算法的原理是，在树中，“已使用节点”表示“已使用（与其父节点之间的）唯一边”。因此，我们实际上标记已使用的边，并不会再次输出它们。

例如，当我们将2和5标记为已使用时，这意味着我们标记了边缘1-2和2-5。然后，当我们进入“1 2 6”时，我们不输出边缘“1-2”，因为它已被使用，但会输出“2-6”。

将根节点（节点1）标记为已使用一次不会影响输出，因为从未检查其值。这有一个物理解释-根节点没有父边。

很抱歉解释不够清楚。很难在没有绘图的情况下解释树上的算法 :) 如有任何关于算法或C＃的问题，请随时提问。

这是工作中的IDEOne演示。

P.S. 这段代码可能不是一个好的和适当的C#代码（避免自动属性，避免LINQ），以使其他编程人员能够理解。

当然，这个算法并不完美-我们可以删除currentPath，因为在树中路径很容易恢复; 我们可以改进输出; 我们可以将此算法封装在类中。我只是试图展示常见的解决方案。