简单图中的递归回溯-Java 学习之路

想象下面的简单图：

graph

每个实体都有一个索引开始计数0（所以A有索引0，B有索引1，依此类推） .

A和B相连，所以它们之间的距离是1，所以f.e . A和D之间的距离是2，因为它们都与F相连 .

如何在java中实现一个方法，它接受两个索引和一个距离作为参数，并执行递归回溯，以便找出给定距离内两个给定实体是否可达？

所以，如果我用参数（3,0,2）调用方法，那么它应该返回true，因为3是D而0是A，它们之间的距离是2，所以它是真的 .

我尝试过的：

public boolean backtracking(int index0, int index1, int d) {

    boolean reachable = relation[index0][index1];

    if (d > 0 && !reachable) {
        for (int i = index0+1; i <= index1+d; i++) {
            backtracking(index0+1, index1, d-1);
        }
    }

    return reachable;
}

我有一个邻接矩阵，其中包含2D-boolean-array关系中的关系，基于图形 .

提前致谢

1 回答

-1

以下代码可以满足您的需求 .

canReach 方法是一种递归方法 . 如果允许的 distance 小于零，那么我们返回false . 如果给予 canReach 的节点等于this，则它是可达的 . 否则，迭代 Node 的邻居，距离减少1 .

Code:

public class Node {
    private Set<Node> neighbours = new HashSet<Node>();

    public Node() {
    }

    public void connect(Node node) {
        if (neighbours.add(node))
            node.connect(this);
    }

    public boolean canReach(Node node, int distance) {
        if (distance < 0)
            return false;
        if (this.equals(node)) {
            return true;
        } else {
            for (Node neighbour : neighbours)
                if (neighbour.canReach(node, distance - 1))
                    return true;
            return false;
        }
    }
}

private Graph() {
    Node a = new Node();
    Node b = new Node();
    Node c = new Node();
    Node d = new Node();
    Node e = new Node();
    Node f = new Node();
    a.connect(b);
    b.connect(c);
    b.connect(e);
    a.connect(f);
    f.connect(d);
    System.out.println(a.canReach(d, 2));

}

public static void main(String[] args) {
    new Graph();
}

Output:

false
true

回复于 2024-04-19T15:31:31+08:00

简单图中的递归回溯

1 回答

相关问题