Да, есть (п) алгоритм вывода.
Подумайте о том, что дерево не тронуто - просто график, где каждый узел имеет двунаправленные ребра, которые не образуют циклов.
Для данного узла p с соседними узлами, скажем a_i, мы вычислим высоты Hpa_i. Высота Hpa_i - это высота поддерева с корнем p (т. Е. Для этой части алгоритма мы временно рассматриваем корневое поддерево), полученное путем рассмотрения узла a_i как родителя p.
Если вас интересует самый длинный путь от каждого узла до листа (ваш вопрос плюс его название оставляет сомнение в том, что вы на самом деле пытаетесь вычислить), это просто max {Hpa_i для всех i}. Соответствующее значение i дает самый длинный путь.
Если с другой стороны, вы заинтересованы в длинном пути через р, что будет суммой наибольших пар, выбранных из {LEN (р - a_i) + Ha_ip для всех я}, и два соответствующих значения 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
Это будет О (п) вычисление, кроме того, потому что она затрачивает постоянную работу по каждому краю, и число ребер в дереве равно п-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();
}
}
Возможная Дубликат [Самый длинный путь между узлами 2] (http://stackoverflow.com/questions/3124566/longest-path-between-2-nodes) – Guido
@Guido Nope, это связанная, но другая проблема. –
Вы хотите найти N таких путей (по одному для каждого узла) и иметь каждый такой путь, представленный его конечными точками? – pkacprzak