0

我正在研究深度优先搜索，我发现的示例正在寻找一个特定的答案，比如说数字 10。

它遍历树丢弃每个不是 10 的节点，并在找到 10 时停止。

是否可以使用深度优先搜索或其他算法来搜索树的每个分支？我希望它运行一个场景并提出一个值并将其存储到一个可能名为highestValue.

然后它将搜索下一个分支并获取一个值并将其存储到一个可能名为 Value 的变量中。然后它将highestValue 与Value 和if (Value > highestValue) highestValue = Value.

它将重复该过程，直到完成运行所有可能的场景。有任何想法吗？我应该提到我正在用 Java 写这个。

4

2 回答 2

0

由于您仍然想知道它是如何工作的，这段代码可能会帮助您解决这个问题。这适用于图表，看看。它对每个节点进行 DFS，但在到达我们要查找的节点时停止。

要获取最大值，只需将最大值存储到 int 变量中，然后继续搜索并将每个节点的数据与 int 变量中的当前最大值进行比较。

public static boolean search(Graph g, Node start, Node end) {
    LinkedList<Node> stack = new LinkedList<Node>();
    for (Node u : g.getNodes()) {
        u.state = State.Unvisited;
    }
    start.state = State.Visiting;
    stack.add(start);
    Node u;
    while (!stack.isEmpty()) {
        u = stack.removeFirst();
        if (u != null) {
            for ( Node v : u.getAdjacent() ) {
                if (v.state == State.Unvisited) {
                    if (v == end) {
                        return true;
                    }
                    else {
                        v.state = State.Visiting;
                        stack.add(v);
                    }
                }
            }
            u.state = State.Visited;
        }
    }
    return false;
}
于 2013-10-20T04:37:48.640 回答
0

如果我们想访问图中的每个节点，DFS 是最简单的。但是，如果我们有一棵非常大的树，并且想要在离原始节点太远时准备退出，则 DFS 可以搜索该节点的数千个祖先，但永远不会搜索所有的子节点。严格来说，这取决于图表中数据的组织方式。资源

于 2013-10-20T03:54:45.793 回答