在单亲、多子图中查找缺少子节点的算法

Question

想象一个数据结构，其中您有一个充满节点的图。

每个节点都有数据、一个父节点和 0+ 个子节点。

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.parent = None
        self.children = []

图表本身处理连接节点

class Graph:
    def __init__(self, node) -> None:
        self.root_node = node

   def add_relationship(self, parent, child):
        if not parent.parent:
            parent.parent = self.root_node
            self.root_node.children.append(parent)

        parent.children.append(child)
        child.parent = parent

对于约束，假设总共有 2 到 100 个节点。

现在，假设我想向图类添加一个方法，该方法返回图中没有子节点的所有节点。

我的第一个想法是递归。

def _end_nodes(self, current_node, nodes_with_children=[], nodes_without_children=[]):
    for node in current_node.children:
        if node.children:
            nodes_with_children.append(node)
        else:
            nodes_without_children.append(node)
    
    if not nodes_with_children:
        return []
    return [nodes_without_children] + self._end_nodes(nodes_with_children.pop(0))

但是无论调用递归函数多少次，这都会重复产生所需的答案。

当然，我可以从返回的数组中获取单个元素

def __repr__(self) -> str:
    return str(self._end_nodes(self.root_node)[0])

但我觉得这样很草率。 我怎样才能以更简洁的方式获得想要的结果？

Answer 1

要查找单父多子图中缺少子节点的节点，可以在 Graph 类中添加一个方法来遍历整个图并收集没有子节点的节点。

该方法定义如下。它基本上使用 BFS。

def find_nodes_without_children(self):
        nodes_without_children = []
        queue = [self.root_node]
        
        while queue:
            current_node = queue.pop(0)
            if not current_node.children:
                nodes_without_children.append(current_node)
            else:
                queue.extend(current_node.children)
        
        return nodes_without_children

你可以通过下面的代码行来验证它

print([node.data for node in graph.find_nodes_without_children()])

总体实现如下所示

    class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.parent = None
        self.children = []

class Graph:
    def __init__(self, node) -> None:
        self.root_node = node

    def add_relationship(self, parent, child):
        if not parent.parent:
            parent.parent = self.root_node
            self.root_node.children.append(parent)
        parent.children.append(child)
        child.parent = parent

    def find_nodes_without_children(self):
        nodes_without_children = []
        queue = [self.root_node]
        
        while queue:
            current_node = queue.pop(0)
            if not current_node.children:
                nodes_without_children.append(current_node)
            else:
                queue.extend(current_node.children)
        
        return nodes_without_children

仅供参考：时间和空间复杂度都是 O(N)