算法 - 树中所有节点的最大距离

Question

所以.. 找到树中两个节点之间的最长路径相当容易。但我想要的是为所有 x 找到从节点 x 到树中另一个节点的最长路径。

这个问题也可以用下面的方式表达:计算给定树的所有有根树的高度。

当然，一种方法是对树中的所有节点执行 BFS/DFS，并为每个节点记住找到的最远节点。但是，这会导致 O(N²)。有没有可能做得更好？

编辑:回顾一下，我的问题不是如何找到图中最长的路径。它是如何在优于 O( N²) 时间复杂度，如果可能的话。

Answer 1

是的，有一个 O(n) 算法。

将树视为无根树 - 只是一个图，其中每个节点都具有不形成循环的双向边。

对于具有相邻节点的给定节点 p，比如 a_i，我们将计算高度 Hpa_i。高度 Hpa_i 是通过将节点 a_i 视为 p 的父节点而获得的子树具有根 p 的高度(即对于这部分算法，我们暂时考虑有根子树)。

如果您对从每个节点到叶子的最长路径感兴趣(您的问题及其标题对您实际尝试计算的内容产生怀疑)，它只是 max{ Hpa_i for all i }。相应的 i 值给出了最长路径本身。

另一方面，如果您对到 p 的最长路径感兴趣，那将是从 { len(p--a_i) + Ha_ip 中为所有 i 选择的最大对的总和}, i 的两个对应值给出了最长路径本身。

因此，如果我们有每个节点的高度，得到最终结果是一个简单的 O(n) 工作。

剩下的只是计算所有节点的高度。为此，从特殊的深度优先搜索开始。它接受 2 个节点作为参数。第一个 p 是正在搜索的节点，第二个 q\in {a_i} 是当前被视为 p 的父节点的相邻节点。设 U 是一个将节点对带到高度的映射:(p, q) -> Hpq

function search_and_label(p, q)
  if ((p, q) maps to height Hpq in U ) { return Hpq }
  if (p == null) { add (p, q) -> 0 to U and return 0 }
  let h = max(all x adjacent to p, not equal to q) {
            len(p--x) + search_and_label(x, p)
          }
  add (p, q) -> h to U
  return h
  

现在我们可以找到所有的高度。

 Add mappings (p, x)->null to U for all nodes p and adjacent nodes x
 Also add a mapping (p, z)->null to U for all nodes p having < 3 adjacent
 while (U contains a mapping of the form (p, x)->null) 
   search_and_label(p, x) // this replaces the null mapping with a height

这也是一个 O(n) 计算，因为它会在每条边上花费不断的工作，而树中的边数是 n-1。

代码

今天下雨了，所以这里有一些代码生成随机树并在 O(n) 时间内用最长路径信息标记它。首先，一个典型的输出。每个节点都标有自己的编号，然后是包含它的最长路径的长度，然后是该路径上相邻节点的编号。小边标签是高度信息。首先是相对子树的高度以及该子树中到叶子的最长路径的节点:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * An undirected graph. It has a builder that fills the graph with a random
 * unrooted tree. And it knows how to decorate itself with longest path
 * information when it's such a tree.
 */
class Graph {

  /**
   * Edge p--q is represented as edges[p][q]=dq and edges[q][p]=dp, where dq and
   * dp are node data. They describe the respective end of the edge:
   * <ul>
   * <li>dq.len == dp.len, the edge length
   * <li>dq.h is the height of subtree rooted at p with q as parent.
   * <li>dq.next is the child of p (with respect to parent q) rooting the max
   * height subtree.
   * </ul>
   */
  final Map<Node, Map<Node, EdgeData>> edges = new HashMap<>();

  /**
   * A node in the graph.
   */
  static class Node {

    final int id; // Unique node id.
    Node a, b;    // Adjacent nodes on longest path.
    double len;   // Length of longest path.

    Node(int i) {
      this.id = i;
    }
  }

  /**
   * Data associated with one end of an edge in the graph.
   */
  static class EdgeData {

    final double len;  // Edge length.
    Double h;          // Subtree height.
    Node next;         // Next node on max length path to leaf.

    EdgeData(double len) {
      this.len = len;
    }
  }

  /**
   * Add a new node to the graph and return it.
   */
  Node addNode() {
    Node node = new Node(currentNodeIndex++);
    edges.put(node, new HashMap<>());
    return node;
  }
  private int currentNodeIndex = 0;

  /**
   * Add an undirected edge between nodes x and y.
   */
  void addEdge(Node x, Node y, double len) {
    edges.get(x).put(y, new EdgeData(len));
    edges.get(y).put(x, new EdgeData(len));
  }

  /**
   * Decorate subtree rooted at p assuming adjacent node q is its parent.
   * Decorations are memos. No subtree is decorated twice.
   */
  EdgeData decorateSubtree(Node p, Node q) {
    Map<Node, EdgeData> adjacent = edges.get(p);
    EdgeData data = adjacent.get(q);
    if (data.h == null) {
      data.h = 0.0;
      for (Map.Entry<Node, EdgeData> x : adjacent.entrySet()) {
        if (x.getKey() != q) {
          double hNew = x.getValue().len + decorateSubtree(x.getKey(), p).h;
          if (hNew > data.h) {
            data.h = hNew;
            data.next = x.getKey();
          }
        }
      }
    }
    return data;
  }

  /**
   * Decorate node p with longest path information. Decorations are memos. No
   * node nor its associated subtrees are decorated twice.
   */
  Node decorateNode(Node p) {
    if (p.a == null) {
      double ha = 0.0, hb = 0.0;
      for (Map.Entry<Node, EdgeData> x : edges.get(p).entrySet()) {
        double hNew = x.getValue().len + decorateSubtree(x.getKey(), p).h;
        // Track the largest two heights and corresponding subtrees.
        if (hNew > ha) {
          p.b = p.a;
          hb = ha;
          p.a = x.getKey();
          ha = hNew;
        } else if (hNew > hb) {
          p.b = x.getKey();
          hb = hNew;
        }
      }
      p.len = ha + hb;
    }
    return p;
  }

  /**
   * Decorate the entire tree. This isn't necessary if the lazy decorators are
   * used as accessors.
   */
  void decorateAll() {
    for (Node p : edges.keySet()) {
      decorateNode(p);
    }
  }

  /**
   * Random tree builder. Parameters are a maximum edge length, tree radius in
   * number of edges, and partitions p[k] giving probabilities of branching with
   * degree k.
   */
  class RandomTreeBuilder {

    final Random gen = new Random();
    final long seed;
    final float[] partitions;
    final int maxLen;
    final int radius;

    RandomTreeBuilder(long seed, float[] partitions, int maxLen, int radius) {
      this.seed = seed;
      this.partitions = partitions;
      this.maxLen = maxLen;
      this.radius = radius;
    }

    private void growTree(Node p, int radius) {
      if (radius > 0) {
        float random = gen.nextFloat();
        float pSum = 0f;
        for (float partition : partitions) {
          pSum += partition;
          if (random < pSum) {
            return;
          }
          Node q = addNode();
          addEdge(p, q, 1 + gen.nextInt(maxLen));
          growTree(q, radius - 1);
        }
      }
    }

    /**
     * Build a tree in the graph. Any existing nodes and edges are erased.
     */
    void build() {
      if (seed != 0) {
        gen.setSeed(seed);
      }
      edges.clear();
      Node p = addNode();
      Node q = addNode();
      addEdge(p, q, 1 + gen.nextInt(maxLen));
      growTree(p, radius);
      growTree(q, radius);
    }
  }

  class TreePrinter {

    PrintStream stream;

    TreePrinter(PrintStream stream) {
      this.stream = stream;
    }

    /**
     * Print graph in the GraphViz DOT language.
     */
    void print() {
      stream.println("graph tree {");
      stream.println(" graph [layout = twopi overlap=false ranksep=1.7]");
      Node p = edges.keySet().iterator().next();
      Node q = edges.get(p).keySet().iterator().next();
      printEdge(p, q);
      print(p, q);
      print(q, p);
      for (Node x : edges.keySet()) {
        printNode(decorateNode(x));
      }
      stream.println("}");
    }

    /**
     * Print edge {@code p--q} in the GraphViz DOT language.
     */
    private void printEdge(Node p, Node q) {
      EdgeData dq = decorateSubtree(p, q);
      EdgeData dp = decorateSubtree(q, p);
      stream.format(" n%d--n%d [label=\"%.0f\" fontsize=8 "
          + "headlabel=\"%.0f:%s\" taillabel=\"%.0f:%s\"]\n",
          p.id, q.id, dq.len,
          dp.h, dp.next == null ? "-" : dp.next.id,
          dq.h, dq.next == null ? "-" : dq.next.id);
    }

    /**
     * Print node p in the GraphViz DOT language.
     */
    private void printNode(Node p) {
      stream.format(" n%d [ label=\"%d (%.0f:%s-%s)\" fontsize=10 ]\n",
          p.id, p.id, p.len,
          p.a == null ? "-" : p.a.id, p.b == null ? "-" : p.b.id);
    }

    /**
     * Print the sub-tree rooted at node p, treating node q as its parent.
     */
    private void print(Node p, Node q) {
      for (Node x : edges.get(p).keySet()) {
        if (x != q) {
          printEdge(p, x);
          print(x, p);
        }
      }
    }
  }

  public static void main(String[] args) throws FileNotFoundException {
    PrintStream stream = args.length > 0
        ? new PrintStream(new File(args[0]))
        : System.out;
    Graph graph = new Graph();
    graph.new RandomTreeBuilder(42L, new float[]{0.3f, 0.1f, 0.3f, 0.2f}, 10, 5)
        .build();
    graph.new TreePrinter(stream).print();
  }
}