-1

我无法编写算法来计算树中独立集的数量。（独立集是任何两个节点之间没有边的地方。）

这是我的 ListNode 的 java 类：

 1public class ListNode
 2{
 3    private Object data;
 4    private ListNode next;
 5
 6    public ListNode(Object data, ListNode next)
 7    {
 8        this.data = data;
 9        this.next = next;
10    }
11
12    public Object getData()  {return data;}
13    public ListNode getNext(){return next;}
14    public void setNext(ListNode n){next = n;}
15    public void setData(Object d){data = d;}
16    public boolean search(ListNode l, Object o)
17    {
18        while (l != null){
19            if (l.getData().equals(o))
20                return true;
21            l = l.getNext();
22        }
23        return false;
24    }
25    public static ListNode rev(ListNode curr)
26    {
27        ListNode rev = null;
28        while (curr != null){
29            rev = new ListNode(curr.getData(), rev);
30            curr = curr.getNext();
31        }
32        return rev;}}

我的 TreeNode 的 java 类：

1public class TreeNode
 2{   ListNode children = null;
 3    public void addChild(TreeNode t)
 4    {
 5        if (children == null)
 6            children = new ListNode(t, null);
 7        else{
 8            ListNode curr = children;
 9            while (curr.getNext() != null)
10                curr = curr.getNext();
11            curr.setNext(new ListNode(t, null));
12        }}
13    public void setChildren(ListNode t){this.children = t;}
14    public int numStableSet()
15    {
16
17        if (children == null || children.getNext() == null)
18            return 2;
19        else{
20            int count = 2;
21            setChildren(children.getNext());
22            count *= numStableSet();
23            return count;
24        }
25    }

numStableSet 方法是我需要一些编码帮助的方法。由于它现在设置，它打印出比正确答案少 1。我还没有弄清楚每个节点本身可能是一棵树的情况。

帮助表示赞赏

4

1 回答 1

1

我不相信你的算法总是会落后一个。让我们考虑几个示例案例，从最简单的案例开始。

  • 无节点 => 1 个独立集，空集
  • 一个节点=> 2个独立集，空的和一个节点
  • 一个父母及其唯一的孩子=> 3个独立的集合，空的和任一节点

由于您的代码似乎为单个节点和具有单个子节点的节点给出了相同的结果 2，我相信您的代码是错误的。

现在让我们考虑递归情况，以找到正确的算法。您当前正在访问给定节点。您可以决定不将该节点包含在稳定集中，然后访问其所有子节点并为这些节点选择任意稳定集。或者您可以决定包含当前节点，但前提是不包含其自己的父节点，并且在递归到子节点时，您必须确保不计算这些节点。跟踪所有可能的方式来组合这些选择，并且你有你的计数。在 pythonic 伪代码中：

def combinationsWithoutCurrent(current):
  num = 1
  for child in current:
    num *= stableSet(child)
  return num

def combinationsWithCurrent(current):
  num = 1
  for child in current:
    num *= combinationsWithoutCurrent(child)
  return num

def stableSet(current):
  return (combinationsWithCurrent(current) +
          combinationsWithoutCurrent(current))

由于您更喜欢 Java 和晦涩难懂的手工容器类，因此这里有一些 Java 代码，说明我猜测您的数据结构的用途。由于您从不调用getData树遍历，因此我在您的代码中看不到任何实际的递归。所以我的猜测可能是错误的。

private int combinationsWithoutCurrent() {
  int num = 1;
  for (ListNode iter = children; iter != null; iter = iter.getNext())
    num *= ((TreeNode)iter.getData()).numStableSets();
  return num;
}

private int combinationsWithCurrent() {
  int num = 1;
  for (ListNode iter = children; iter != null; iter = iter.getNext())
    num *= ((TreeNode)iter.getData()).combinationsWithoutCurrent();
  return num;
}

public int numStableSet() {
  return combinationsWithCurrent() + combinationsWithoutCurrent();
}
于 2013-10-06T23:29:23.237 回答