图论--寻找子图

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);
    }
}

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

我还在考虑扩展到使用Neo4j数据库，但我想先在本例中解决这个问题。

谢谢!

Answer 1

您正在寻找的是最底层的公共祖先：

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

我可以尝试详细地解释它，但我永远不会比本教程做得更好、更全面，它教会了你许多不同的算法来解决这个问题：

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