深度优先算法从起点

Question

好的，我在网上看了很多，但我真的不喜欢它。

我有一个 ArrayList towns = new ArrayList<Town>，其中包含我将对其执行 DFS 的城镇。

我用 ~8 个城镇填充这个数组

我有一个整数 int i（ArrayList 中的城镇索引，是路径中的第一个）

我有一个初始距离double dist = 0

我有一个函数 distBetween(Town a, Town b) 可以按照它说的去做。

我有一个 Arraylist route = new ArrayList<Town>()，其中包含城镇的顺序，具体取决于我所走的路径。

现在我有了执行深度优先搜索的主要功能（递归，根据在线研究）。

public static void dfs(){

    // what goes here

}

我需要将城镇添加到路线数组中，并根据深度优先搜索算法将其移除。我还需要编辑 dist 变量。

我怎么会知道这个。有人可以向我提供一些伪代码或评论来解释该怎么做。我似乎无法应用我在网上找到的其他算法。如果我能得到针对我的情况的解释，那就太好了。

我可以从 town 中删除索引 i，如果这样可以更轻松地执行搜索。

Answer 1

DFS算法

输入图G = (V, E)的顶点和边。
输入源顶点并将其赋值给变量S。
将源顶点压入堆栈。
重复步骤 5 和 6，直到堆栈为空。
弹出栈顶元素并显示。
如果不在队列中并显示（即；未访问），则将与刚刚弹出的元素相邻的顶点推送。
退出。

要存储顶点和边，您需要 adjacency matrix。

Answer 2

我假设你有一个 State class 具有以下属性（如果你喜欢图表，请使用 Node 而不是 State）：

Set<Town> unused;        // towns not yet visited
ArrayList<Town> path;    // current path
double dist;             // total distance in path

然后使用像这样的代码递归地尝试使用 DFS 的每条可能路径。在第一次调用时，使用 dfs(emptyState, startTown, null):

public static void dfs(State s, Town last, State best) {
    s.path.add(last);
    s.unused.remove(last);
    if (unused.empty()) {
        // all towns visited - distance and path are now complete
        if (best == null || s.dist < best.dist) best = s;
        return;
    }
    for (Town t : s.unused) {
        State next = s.copy(); // a copy of State s
        next.dist += distBetween(last, t);
        dfs(next, t);
    }
}

调用此函数后，所有路径都将恰好访问一次（按 DFS 顺序），best 将包含最短路径。当心，对于许多城市来说，这变得非常慢 - O(n!)。

深度优先算法从起点

Depth First Algorithm from starting point

java

algorithm

graph-theory

arraylist

depth-first-search