时间戳

首页 > 解决方案 > 这个 DFS 实现有什么问题？

python - 这个 DFS 实现有什么问题？

问题描述

我不确定以下深度优先搜索代码有什么问题。最后包含预期的 vs 程序输出。我通过运行来自 geeksforgeeks 的代码获得了预期的输出（s/o to them）。任何帮助，将不胜感激。这是我的代码：

class Node:
    def __init__(self, val):
        self._val = val
        self._chdrn = []

class Nary:

    def __init__(self, n: int):
        self._n = n
        self._root = None

    def insert(self, val: int):
        nn = Node(val)
        if not self._root:
            self._root = nn
        else:
            def recur(parent: Node):
                print("Parent: ", parent._val)
                if len(parent._chdrn) < self._n:
                    parent._chdrn.append(nn)
                    return 1
                else:
                    for chdl in parent._chdrn:
                        ret = recur(chdl)
                        if ret == 1:
                            break
            parent = self._root
            recur(parent)

    def dfs(self):
        def _dfs(node: Node):
            if not node: return
            print(node._val, end=' ')
            for chld in node._chdrn:
                # print("current child = ", chld._val)
                _dfs(chld)
        _dfs(self._root)

Tree  = Nary(3)
for i in range(10): Tree.insert(i)
Tree.dfs()
#

预期输出：0 1 4 5 6 2 7 8 9 3
程序输出：0 1 4 7 8 9 5 6 2 7 8 9 3

标签： pythondepth-first-search

解决方案

您的 DFS 代码没有任何问题。您使用该方法构建的树insert是错误的。

循环遍历recur. 否则同一个节点将被插入到多个父节点下。

class Node:
    def __init__(self, val):
        self._val = val
        self._chdrn = []


class Nary:

    def __init__(self, n: int):
        self._n = n
        self._root = None

    def insert(self, val: int):
        print(f"Inserting {val}")
        nn = Node(val)
        if not self._root:
            self._root = nn
        else:
            def recur(parent: Node):
                if len(parent._chdrn) < self._n:
                    print(f"Added under parent: {parent._val}")
                    parent._chdrn.append(nn)
                    return 1
                else:
                    for chdl in parent._chdrn:
                        ret = recur(chdl)
                        if ret == 1:
                            return 1  # not just break

            parent = self._root
            recur(parent)

    def dfs(self):
        def _dfs(node: Node):
            if not node: return
            print(node._val, end=' ')
            for chld in node._chdrn:
                # print("current child = ", chld._val)
                _dfs(chld)

        _dfs(self._root)


Tree = Nary(3)
for i in range(10): Tree.insert(i)
Tree.dfs()

顺便说一句，这棵树的正确 DFS 顺序是：

0 1 4 7 8 9 5 6 2 3

您应该画出树并手动执行 DFS 来验证。

推荐阅读