是的，有一个 O(n) 算法。
将树视为无根树 - 只是一个图，其中每个节点都有不形成循环的双向边。
对于具有相邻节点的给定节点 p（例如 a_i），我们将计算高度 Hpa_i。 Height Hpa_i 是子树的高度带根 p（即，对于算法的这一部分，我们暂时考虑有根子树）通过将节点 a_i 视为 p 的父节点而获得。
如果您对从每个节点到叶子的最长路径感兴趣（您的问题加上其标题让人怀疑您实际要计算的内容），那么它只是 max{ Hpa_i for all i }。相应的 i 值给出了最长的路径本身。
另一方面，如果您对最长路径感兴趣throughp，这将是从 { len(p--a_i) + Ha_ip for all 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。
Code
今天下雨了，所以这里有一些代码可以生成一棵随机树，并在 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();
}
}
