连接图形矩阵中的节点

Question

你好我正在做这个小项目，它需要我在 Java 中构建一个类似于棋盘的矩阵。我应该让骑士从一个点到达另一个点（以骑士移动的方式）。所以我需要找到最短的路才能到达那里。

我的问题是，我无法连接边缘以到达该点。我可以查明顶点是否是有效移动，但我似乎无法找到创建节点以到达该点的方法。例如，

0 XXXXX

1 XXXOX

2 XXXXX

3 XXKXX

4 XXXXX

5 XXXXX

我需要创建连接 K 和 O 的节点，以便稍后找出最短距离。 PS。我会接受如何到达那里的提示或一些提示。真的不需要确切的代码。非常感谢你！我知道上面的矩阵表示不好，但请不要批评我

Answer 1

棋盘可以用二维数组来实现。矩阵中的每个单元格都可以被认为是图中的一个节点（或顶点）。边由两个节点（在本例中为两个单元格）组成，一个是 from 或 source [我们称之为 Nod A]，另一个是 to 或 neighbor 或destination 节点 [ 我们称之为节点 B]。

如果有可能从 node A 移动到 node B，则 Edge 退出。

您可以使用 Dijkstra's algorithm。 http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-dijkstras.html

对于具有 Knight 位置的节点，您可以看到 Knight 可以移动到并添加到最小堆的单元格的可能性。每条边的权重是恒定的。您只需要更新节点的成本。

Answer 2

经典的Breadth-First-Search可能是最简单的方法：

class Location {
    int x;
    int y;

    List<Location> adjacent() {
        // TODO return list of locations reachable in a single step
    }
}

List<Location> findShortestPath(Location start, Location destination) {
    Location[][] previous = new Location[8][8];

    Deque<Location> queue = new ArrayDeque<>();
    queue.add(start);
    do {
        Location loc = queue.poll();
        for (Location n : loc.neighbors()) {
            if (previous[n.x][n.y] == null) {
                previous[n.x][n.y] = loc;
                queue.add(n);

                if (n.x == destination.x && n.y == destination.y) {
                    // we've found a way, let's reconstruct the list of steps
                    List<Location> path = new ArrayList<>();
                    for (Location l = n; l != start; l = previous[l.x][l.y]) {
                        path.add(l);
                    }
                    path.reverse();
                    return path;
                }
            }
        }
    } while (!queue.isEmpty());
    return null; // no path exists
}

此代码从起始位置枚举所有路径。因此，如果有到达目的地的路径，它就会找到它。此外，因为路径是按顺序或升序列举的，所以第一个这样的路径将是最短的。

连接图形矩阵中的节点

Connecting nodes in a matrix for a graph

java

graph

matrix

jgrapht

vertices