家谱祖先查找算法

Question

我的方法无法通过单元测试。我盯着它看了5个小时都是白费力气。有没有人能帮我看看出了什么问题？

PS:下面代码中的getAllRelations()方法是将格式化的输入分隔到字符串的ArrayList数组列表中，例如，如果我有这样的格式化输入(我在无法通过的测试用例中使用了它)

String format = "John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson";

在每一行中，第一人称是第二人称的父级。getAllRelations()方法将这个格式化的字符串拆分成数组列表，每个列表只包含每行中的两个名称字符串(名称前后没有空格)作为其元素。例如，arraylist1将是一个包含“John”和"Mary Smith“的列表。

这是我的方法，我不知道哪里出了问题，我想用这个方法来检查两个人是否有相同的祖先。

private boolean hasSameAncestor(String person1, String person2){
    ArrayList<ArrayList<String>> allRelations = allRelations();
    int i = 0;
    int j = 0;
    String name1 = person1;
    String name2 = person2;
    String parent1;
    String parent2;
    for(i = 0, parent1 = ""; i < allRelations.size(); i++){
        if(name1.equals(allRelations.get(i).get(1))){
            parent1 = allRelations.get(i).get(0);
            for(j = 0, name2 = person2, parent2 = ""; j < allRelations.size(); j++){
                if(name2.equals(allRelations.get(j).get(1))){
                    parent2 = allRelations.get(j).get(0);
                    if(parent2.equals(parent1)){
                        return true;
                    }
                    else{
                        name2 = parent2;
                        j = 0;
                    }
                }
            }
            name1 = parent1;
            i = 0;
        }
    }
    return false;
}

我不能通过的测试用例是这样的。

    @Test
    public void testHasSameAncestor()
    FamilyTree familyTree4 = new FamilyTree("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
    assertEquals(true, format.hasSameAncestor("Max Jackson", "Robert Andrew"));
}

我找不到我的功能出了什么问题，有人能帮我吗？非常感谢。

可以粘贴到eclipse以获得调试帮助的代码。

package test;

import java.util.ArrayList;
import java.util.Arrays;


public class Test1 {

    String test;

    public Test1(String test){
        this.test = test;
    }


    private ArrayList<String> lineRelations(){
        int i;
        ArrayList<String> lineRelations = new ArrayList<String>();
        String[] lines = test.split("\n");
        for(i = 0; i < lines.length; i++){
            lineRelations.add(lines[i]);
        }
        return lineRelations;
    }

    private ArrayList<ArrayList<String>> allRelations(){
        int i;
        ArrayList<ArrayList<String>> allRelations = new ArrayList<ArrayList<String>>();
        ArrayList<String> lineRelations = lineRelations();
        for(i = 0; i < lineRelations.size(); i++){
            ArrayList<String> eachLine = new ArrayList<String>(Arrays.asList(lineRelations.get(i).split("\\s*,\\s*")));
            allRelations.add(eachLine);
        }
        return allRelations;
    }

    public boolean hasSameAncestor(String person1, String person2){
        ArrayList<ArrayList<String>> allRelations = allRelations();
        int i = 0;
        int j = 0;
        String name1 = person1;
        String name2 = person2;
        String parent1;
        String parent2;
        for(i = 0, parent1 = ""; i < allRelations.size(); i++){
            if(name1.equals(allRelations.get(i).get(1))){
                parent1 = allRelations.get(i).get(0);
                for(j = 0, name2 = person2, parent2 = ""; j < allRelations.size(); j++){
                    if(name2.equals(allRelations.get(j).get(1))){
                        parent2 = allRelations.get(j).get(0);
                        if(parent2.equals(parent1)){
                            return true;
                        }
                        else{
                            name2 = parent2;
                            j = 0;
                        }
                    }
                }
                name1 = parent1;
                i = 0;
            }
        }
        return false;
    }
}

测试用例

package test;
import static org.junit.Assert.*;
import test.Test1;

import org.junit.Test;


public class Test1Test {

    @Test
    public void testHasSameAncestor(){
        Test1 test1 = new Test1("John Doe , Mary Smith" + "\n" + "Brian William , John Doe" + "\n" + "Brian William ,Robert Andrew" + "\n" + "Mary Smith , Max Jackson");
        assertEquals(true, test1.hasSameAncestor("Max Jackson", "Robert Andrew"));
    }
}

Answer 1

首先找到两个人的基本祖先，然后比较它们。

请检查:)

public boolean hasSameAncestor(String person1, String person2) {
        ArrayList<ArrayList<String>> allRelations = allRelations();
        int i = 0;
        String name1 = person1;
        String name2 = person2;
        String parent1;
        String parent2;

        //Find first person's ancestor
        for (i = 0, parent1 = ""; i < allRelations.size(); i++) {
            if (name1.equals(allRelations.get(i).get(1))) {
                parent1 = allRelations.get(i).get(0);
                name1 = parent1;
                i = -1; // because i will increase before start new loop
            }
        }

        //Find second person's ancestor
        for (i = 0, parent2 = ""; i < allRelations.size(); i++) {
            if (name2.equals(allRelations.get(i).get(1))) {
                parent2 = allRelations.get(i).get(0);
                name2 = parent2;
                i = -1;
            }
        }
        System.out.println(parent1);
        System.out.println(parent2);
        if (parent1.equals(parent2)) {
            return true;
        }
        return false;
    }

谨致问候。

Answer 2

首先，您正在使用的数据结构对于这种应用程序来说是可怕的。您应该为您的家谱构建一个实际的数据结构，而不是将所有内容打包成一个字符串，然后拆分该字符串并在一个双for循环中对其进行处理。

在信息学中，树是您想要用于此任务的结构类型。树有两种不同类型的对象：

1) A Node, which has two children, that are also Nodes.
2) A Leaf, which has no children.

您可以使用这些节点对您的家谱树进行建模，然后应用已知的众多树算法之一。(类似的问题是Intersection of 2 binary search trees)

更具体地说:模型中的每个人都会有另外两个人被定义为他们的父母。叶子是没有(已知的)父母的人。然后，您可以运行一个算法来计算两个二叉树的交集。如果交叉点是空的，则它们没有共同的祖先。

Answer 3

你的内部循环总是从1开始。

在循环中使i= -1，j= -1而不是0将会求解。