java - 图论 - 查找子图

Question

我正在编写一个程序，它接受一些名称输入并查看以下结构的树:

                                                        John
                                                    /           \
                                                  Chris         Bob
                                                /   |   \        |  \
                                               Tom Ben  Anna    Jade  Ed
                                               /  \      |           /  \
                                            Will  Mark  Ant        Andy  Dan

程序应返回根节点是输入名称之间最低关系/链接的子树。

如果我输入Mark和Ant，程序应该返回以下树:

                                                  Chris 
                                                /       \   
                                               Tom     Anna     
                                                  \      |         
                                                  Mark  Ant 

如果我输入 Will、Mark 和 Andy，那么程序应该返回以下树:

                                                        John
                                                    /           \
                                                  Chris         Bob
                                                /                   \
                                               Tom                   Ed
                                               /  \                  /  
                                            Will  Mark             Andy  

我使用以下类作为我的树节点和连接:

import java.util.ArrayList;
import java.util.List;

public class Person {
    private String name; 
    private List<Person> children;

    public Person(String name) { 
        this.name = name; 
        children = new ArrayList<Person>();
    }

    public String getName() {
        return name;
    }
    public List<Person> getChildren() {
        return children;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setChildren(List<Person> children) {
        this.children = children;
    }
    public void addChild(Person c) { 
        children.add(c);
    }
}

我的问题是如何解决确定公共(public)节点的问题(第一个实例是 Chris，第二个实例是 John)，以及如何使用该名称来获取子树(公共(public)节点和下面的节点)。

我也在考虑对此进行扩展以使用 Neo4j 数据库，但想首先在这种情况下解决它。

谢谢!

Answer 1

您正在寻找的是最低的共同祖先:

http://en.wikipedia.org/wiki/Lowest_common_ancestor

我可以尝试详细解释它，但我永远无法比本教程做得更好、更全面，它教您许多不同的算法来解决该问题:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor