时间戳

首页 > 解决方案 > java中从0开始的树中最长的路径

java - java中从0开始的树中最长的路径

问题描述

我有一棵树，有 N 个节点和连接它们的 N-1 个链接。

节点用 [0 到 N-1] 范围内的不同数字标记

链接以这样一种方式连接节点，即每对不同的节点通过直接链接或沿着由直接链接组成的路径连接。

从任何其他节点到达任何节点只有一种方法。

现在我的任务起始节点是 0。我想访问尽可能多的节点。我不想多次访问任何节点，我只能沿着直接链接移动。根据我的任务，我可能会在任何节点结束，我只是想找到可能的最长路径。

但是我这里有一个限制，我的逻辑中最多可以访问一个奇数节点（1、3、5 等）。

我的程序的输入表示为数组“A”，这样：

A[0] = 0;
A[P] = Q and P!= 0, then there is a direct link between nodes P & Q.

具有 10 个节点和 9 个链接的示例：

Lets say A={0,9,0,2,6,8,0,8,3,0};


4--6--0--2--3--8--5
      |        |
      9        7
      |
      1(one)


This example should return 4, as there is a longest path 0->2->3->8. Node 3 is the only odd numbered node here.

示例 2：

A = [0,0,0,1,6,1,0,0]

          7 
          |     
    5--1--0--6--4   
       |  |
       3  2 

This example should return 3, as there is a path longest 0->6->4.

我想出了下面的代码来解决这个程序：

public static int longestPath(int[] T) {
        List<Integer>[] nodes = new ArrayList[T.length];

        for (int i = 0; i < T.length; i++) {
            nodes[i] = new ArrayList<>();
        }
        for (int i = 0; i < T.length; i++) {
            if (T[i] != i) {
                nodes[i].add(T[i]);
                nodes[T[i]].add(i);
            }
        }
        List<Integer> connectedNodes = nodes[0];

        int longestPath = 0;
        for (int i = 0; i < connectedNodes.size(); i++) {
            int nextNode = connectedNodes.get(i);
            int count = 1;
            Set<Integer> set = new HashSet<>();
            set.add(0);
            set.add(nextNode);
            int odds = 0;
            if (nextNode % 2 != 0) {
                odds++;
            }
            count++;
            while (true) {
                List<Integer> arrayList = nodes[nextNode];
                arrayList.sort(null);
                int next = arrayList.get(arrayList.size() - 1);
                if (!set.contains(next)) {
                    set.add(next);
                    if (next % 2 != 0) {
                        odds++;
                        if (odds >= 2) {
                            break;
                        }
                    }
                    count++;
                    nextNode = next;
                } else {
                    break;
                }
            }
            longestPath = Math.max(count, longestPath);
        }

        return longestPath;
    }

当我在上个月的一次考试中尝试这个程序时，这个程序只适用于这 2 个测试用例，但它失败了我不知道的其他测试用例，并且得到了 16 分（满分 100）。

我正在努力弄清楚我的代码中的正确方法和问题。

你能帮我看看这段代码有什么问题以及如何解决这个问题。我还想打印实际最长的路径0->2->3->8，例如 1 和0->6->42。

标签： javaalgorithmtree

解决方案

您可以通过深度优先搜索找到答案。

最初，您必须将输入数组转换为邻接列表，稍后将在深度优先搜索中使用该列表。你可以这样做：

List<List<Integer>> tree = new ArrayList<>();

int longestPath(int[] T) {
  int n = T.length;
  for (int i = 0; i < n; i++) {
    tree.add(new ArrayList<>());
  }
  //we do this to denote that there is an edge between u and T[u] and vice-versa
  for (int u = 0; u < n; u++) {
    if (u != T[u]) {
      tree.get(u).add(T[u]);
      tree.get(T[u]).add(u);
    }
  }

  return recurse(0, -1, false);
}

在每一步，您都需要知道您当前在哪个节点（调用它node），是您从哪个节点跳转到当前节点（调用它parent）和一个标志，告诉您是否已经访问过一个odd有价值的节点（boolean seeOdd参数）。

问题的答案是在给定约束的情况下您可以达到的最深节点的级别。

这是递归深度优先搜索代码：

int recurse(int node, int parent, boolean seenOdd) {
  //if we enter an odd numbered node and we have already 
  //visited another odd-valued one, then we cannot proceed and just return 0
  if (seenOdd && node % 2 == 1) return 0;

  //find out how deep can we go, given the restriction
  //we can visit at most one odd-valued node
  int max = 0;
  for (int next : tree.get(node)) if (next != parent) {
    max = Math.max(max, recurse(next, node, seenOdd | (node % 2 == 1));
  }

  //we add 1 to the answer, because we should 
  //also count the node we are currently at
  return 1 + max;
}

当我们从0没有父节点的 node 开始时（即我们可以用它-1来显示它），我们调用recurse(0, -1, false);.

推荐阅读