计算到其他相同类型节点的距离

Question

我正在编写一个程序来计算 2 个节点（本例中的人）彼此之间的距离。

public class Person() {
    private Set<Person> persons;

    public int calculateDistanceTo(Person person) {
        // how to do this
    }

我尝试使用递归。但这会导致程序无休止地继续下去。

这是（无效代码）。

public int calculateDistanceTo(Person person, int count) {

    if (persons.contains(person)) return 0;

    for (Person p : persons) {
        count += p.calculateDistanceTo(p, ++count);
    }

    return count;
}

Answer 1

(public class Person() 在 Java 中语法不正确)

首先，让我们看看下面的循环在做什么：

for (Person p : persons) {
    count += p.calculateDistanceTo(p, ++count);
}

以如下关系为例：

在上面的例子中，设 1 为 p1，2 为 p2，等等。P1 和 P4 没有链接，所以当你这样做时：

p1.calculateDistanceTo(p4, 0);

递归堆栈为：

calculateDistanceTo(2,1)
    calculateDistanceTo(1,2)
        calculateDistanceTo(2,3)
        … infinite

这就是你进入无限循环的原因。

更正： 1）如果一个人被访问过，你需要给一个人添加一个标志 2）应该用for循环来判断被访人到目标人的最短距离

所以本质上，它是一种深度优先搜索，通过一些比较来给出最短路径。（当然，要在一个距离内找到最短路径，我们应该使用广度优先搜索。但是我根据你给出的解决方案推导出深度优先搜索）

例如：

public class Person {
private Set<Person> friends;

int id;
boolean visited = false;

public Person(int id) {
    this.id = id;
    friends = new HashSet<>();
}

public Set<Person> getFriends() {
    return friends;
}

@Override
public String toString() {
    return id + "";
}

public boolean equals(Object o) {
    return ((Person) o).id == this.id;
}

public int calculateDistanceTo(Person person) {
    this.visited = true;
    if (friends.contains(person)) return 0;

    int shortestDistance = Integer.MAX_VALUE / 2;
    for (Person friend : friends) {
        if (!friend.visited) {
            int dist = friend.calculateDistanceTo(person);
            if (dist < shortestDistance) {// finding the shortest distance
                shortestDistance = dist;
            }
        }
    }

    return 1 + shortestDistance;
}

static Person p1 = new Person(1);
static Person p2 = new Person(2);
static Person p3 = new Person(3);
static Person p4 = new Person(4);
static Person p5 = new Person(5);

public static void main(String[] args) {
    List<Person> persons = new ArrayList<>(Arrays.asList(p1, p2, p3, p4, p5));

    p1.getFriends().add(p2);
    p1.getFriends().add(p3);

    p2.getFriends().add(p1);
    p2.getFriends().add(p3);

    p3.getFriends().add(p1);
    p3.getFriends().add(p2);
    p3.getFriends().add(p5);

    p5.getFriends().add(p3);

    int dist = p1.calculateDistanceTo(p4);
    System.out.println(dist); // 1073741824 means no relation

    for (Person p : persons) p.visited = false;// clear flag

    dist = p1.calculateDistanceTo(p2);
    System.out.println(dist); // 0

    for (Person p : persons) p.visited = false;// clear flag

    dist = p1.calculateDistanceTo(p5);
    System.out.println(dist); // 1
}
}

Answer 2

BOND的答案是可行的，但是在实现上有一个很大的问题：对象的内部状态会在计算过程中被修改。在多线程环境中，这将导致意外行为。所以这是我的解决方案。

首先是 class 人（我存储了一个名字并调用了集合 'neighbours':

public class Person {
    private final Set<Person> neighbours = new HashSet<>();
    private final String name;

    public Person(String name) {
        this.name = name;
    }
    public void addNeighbour(Person p)
    {
        neighbours.add(p);
        p.neighbours.add(this);
    }
    public int calculateDistanceTo(Person p)
    {
        return calculateDistanceTo(p, 0, Collections.emptySet());
    }
    private int calculateDistanceTo(Person person, int count, Set<Person> tried)
    {
        if (neighbours.contains(person))
            return count;
        Set<Person> nextTry = new HashSet<>(tried);
        nextTry.add(this);
        return neighbours.stream()
                .filter(p -> !nextTry.contains(p))
                .mapToInt(p -> p.calculateDistanceTo(person, count+1, nextTry))
                .filter(i -> i>=0)
                .findFirst()
                .orElse(-1);
    }
    @Override
    public String toString() {
        return "Person{" + "name=" + name + '}';
    }
}

我正在创建一组我已经尝试过的人，并将此集合放入 calculateDistanceTo 方法中。如果两个人没有联系，我的方法将 return -1。所以我的 main() 方法将如下所示：

public static void main(String ... args)
{
    Person p1 = new Person("Anton");
    Person p2 = new Person("Berta");
    Person p3 = new Person("Charlie");
    Person p4 = new Person("Dora");
    Person p5 = new Person("Emil");

    p1.addNeighbour(p2);
    p1.addNeighbour(p3);

    p2.addNeighbour(p3);

    p3.addNeighbour(p5);
    System.out.println("Distance from Anton to Dora = "+p1.calculateDistanceTo(p4)); // -1
    System.out.println("Distance from Anton to Berta = "+p1.calculateDistanceTo(p2)); // 0
    System.out.println("Distance from Anton to Emil = "+p1.calculateDistanceTo(p5)); // 1
}

编辑如您所见，没有必要实现 equals() 和 hashCode()，因为我们这里只使用引用。

计算到其他相同类型节点的距离

Calculate distance to other node of same type

java

recursion

distance

set

nodes