算法-树中所有节点的最大距离 [英] Algorithm - maximum distance in tree for all nodes
问题描述
因此..查找树中两个节点之间的最长路径相当容易.但是我想为所有x找到从节点x到树中另一个节点的最长路径.
So.. finding the longest path between two nodes in a tree is fairly easy. But what I want is to find the longest path from node x to another node in the tree, for all x.
这个问题也可以用以下方式表达:计算您可以从给定树上制作的所有有根树的高度.
This problem can also be expressed in the following way: compute the heights of all rooted trees you can make from a given tree.
当然，一种方法是对树中的所有节点执行BFS/DFS，并记住每个节点中找到的最远的节点.但是，这导致O(N 2 ).有可能做得更好吗?
One way, of course, is to just do, for all nodes in the tree, a BFS/DFS and remember for each of them the furthest node found. However, this results in O(N2). Is it possible to do better?
回顾一下，我的问题是否怎么在图中找到最长的路径.如何找到包含给定节点x 对于所有节点x的最长路径，其路径大于大于 O(N 2 )时间复杂度，如果可能的话.
just to recap, my question is NOT how to find the longest path in the graph. It is how to find the longest path containing a given node x FOR ALL nodes x in BETTER THAN O(N2) time complexity, if possible.
推荐答案
是的，有一种O(n)算法.
Yes, there's an O(n) algorithm.
认为树是无根的-只是一个图形，其中每个节点都有不形成循环的双向边.
Think of the tree as unrooted - just a graph where each node has bi-directional edges that form no cycles.
对于具有相邻节点(例如a_i)的给定节点p，我们将计算高度Hpa_i.高度Hpa_i是具有根p 的子树的高度(即，对于算法的这一部分，我们暂时考虑一个有根的子树)，该高度通过将节点a_i视为p的父级而获得.
For a given node p with adjacent nodes, say a_i, we will compute heights Hpa_i. Height Hpa_i is the height of the subtree with root p (i.e. for this part of the algorithm, we temporarily consider a rooted subtree) obtained by considering node a_i to be p's parent.
如果您对从每个节点到叶子的最长路径感兴趣(您的问题及其标题使您对实际上要计算的内容存有疑问)，那么这就是max {Hpa_i for all i}.相应的i值本身给出了最长的路径.
If you're interested in the longest path from each node to a leaf (your question plus its title leaves doubt about what you're actually trying to compute), it's just max{ Hpa_i for all i }. The corresponding i value gives the longest path itself.
如果另一方面，您对通过 p的最长路径感兴趣，那将是从{len(p--a_i)+ Ha_ip对所有i选择的最大对的总和}，而i的两个对应值本身给出了最长的路径.
If on the other hand, you're interested in longest path through p, that will be the sum of the largest pair selected from { len(p--a_i) + Ha_ip for all i }, and the two corresponding values of i give the longest path itself.
因此，如果我们有每个节点的高度，则获得最终结果将是一个简单的O(n)工作.
Thus, if we have the heights for each node, getting the final result is a simple O(n) job.
仅保留所有节点的高度.为此，从特殊的深度优先搜索开始.它接受2个节点作为参数.第一个p是要搜索的节点，第二个q \ in {a_i}是当前被视为p的父节点的相邻节点.令U为一个将节点对提高到高度的地图:(p，q)-> Hpq
It remains only to compute the heights for all nodes. For this, start with a special depth-first search. It accepts 2 nodes as parameters. The first, p, is the node being searched, and the second, q \in {a_i}, is the adjacent node currently bein considered as parent of p. Let U be a map taking node pairs to heights: (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
现在我们可以找到所有的高度.
Now we can find all the heights.
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.
This will be an O(n) computation, also, because it expends constant work on each edge, and the number of edges in a tree is n-1.
代码
今天下雨了，所以这里有一些代码可以生成一棵随机树，并用O(n)时间中最长的路径信息标记它.首先，是典型的输出.每个节点都标有自己的编号，然后是包含它的最长路径的长度，然后是该路径上相邻节点的编号.小边缘标签是高度信息.首先，是对面子树的高度以及该子树中通往叶子的最长路径的节点:
It rained today, so here is some code that generates a random tree and labels it with longest path info in O(n) time. First, a typical output. Each node is labeled with its own number, then the length of a longest path that contains it, followed by numbers of the adjacent nodes on that path. The small edge labels are the height information. First there is the height of the opposite subtree along with the node that's the longest path to leaf in that subtree:
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();
}
}
这篇关于算法-树中所有节点的最大距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
