x 到树中另一个节点的最长路径，对于所有的 x。x 的最长路径，对于所有节点 x。现在需要计算所有节点的高度。为此，从一个特殊的深度优先搜索开始。它接受两个节点作为参数。第一个节点p是正在搜索的节点，第二个节点q ∈ {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
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();
}
}
if ((p, x) maps to height Hpx in U ) 只是在检查是否已经计算并存储了(p, x)的高度值在备忘录表中，而不是将查找结果与Hpx的某个计算值进行比较。你可能需要稍微明确一下这一点。 - j_random_hackerM（最大深度）。M(X) = 0 IF X DOES NOT EXIST
EXIST(X) = 1 IF X EXISTS, 0 OTHERWISE
M = MAX(EXIST(LEFT) + M(LEFT), EXIST(RIGHT) + M(RIGHT))
第二遍 递归地遍历所有节点，并设置 R（通过树中任何根的最大距离），通过取子节点的最大2个值的总和，然后加上如果存在于任一子节点上的路径的距离。
IF SUM(EXIST(..)) = 0 THEN R = 0
IF SUM(EXIST(..)) = 1 THEN R = X.M + 1 WHERE EXIST(X) = 1
R = SUM(MAX2(x,y: x.M >= y.M >= ..)) + EXIST(x) + EXIST(y)
R: the node max distance through.
M: the node max depth.
最终遍历递归地遍历所有节点，并在树中找到R的最大值。
R(NULL) = 0
R(THIS) = R OF THE CURRENT NODE
S = MAX(R(THIS), S(CHILD1), .. S(CHILDX))
复杂度
TIME = N + N + N = 3N
TIME ~ O(N)