python中的递归搜索

Question

我正在尝试在这种情况下实现搜索算法： 假设有5个人：0-4个人，人们只知道谁直接在他们下面工作。例如，人员0和1不管理任何人，人员2管理人员0，人员3管理人员1，而人员4同时管理人员2和3。在

假设我将这个层次结构存储在名为hierarchyhierarchy = [[],[],[0],[1],[2,3]]的列表中

我要找的是谁直接或间接地在一个任意的人手下工作，在这种情况下，直接或间接在4岁以下工作的人应该是0，1，2，3，或{}。在

我认为这个问题的解决方法是某种递归搜索，但我对递归的理解很模糊。我要找的算法在重复值的情况下也应该是有效的（例如假设3同时管理0,1，答案仍然应该是0,1,2,3）。在

我知道我应该把我的解决方案放在第一位，但我真的不知道如何解决这个问题。。。任何帮助将不胜感激。在

更新：我也很有兴趣找到所有的直接和间接管理一个特定的人。在

Answer 1

如果我们假设一个自上而下的层次结构，这就足够了：

people = [[],[],[0],[1],[2,3]]

def manages(manager, people):
  lst = people[manager]
  for employee in lst:
    lst = lst + manages(employee, people)
  return lst

print(set(manages(4, people)))

输出：{0, 1, 2, 3}

这是一个正在工作的example。在

如果输入列表中存在循环关系，则此解决方案不会终止。在

Answer 2

解决方案

考虑到您想要双向搜索（即能够同时搜索下属和经理），您将需要某种类型的树结构，对节点之间的双向链接进行编码。下面是一个实现这样一个树的类：

class Node:
    def __init__(self, val):
        """initialize a node with the worker id value
        """
        self._children = []
        self._parent = None
        self.val = val

    def link(self, *node):
        """create a parent-child link between this (parent) node and one
        or more (children) nodes
        """
        for n in node:
            n._parent = self
            self._children.append(n)

    def get(self):
        """depth-first recursive get
        """
        return [x for y in ([n.val] + n.get() for n in self._children) for x in y]

    def getparents(self):
        """walks up parents (currently there's at most one parent per-node)
        """
        return [] if self._parent is None else [self._parent.val] + self._parent.getparents()

class Tree:
    def __init__(self, idlists):
        """initialize the tree as per the OP's example input
        """
        self._nodes = {}
        for topid,idlist in enumerate(idlists):
            self.add(topid, idlist)

    def __getitem__(self, key):
        return self._nodes[key]

    def _getnode(self, i):
        """get or create the node with id=i.
        Avoid constructing new Nodes if we don't have to 
        """
        if i in self._nodes:
            return self._nodes[i]
        else:
            n = self._nodes[i] = Node(i)
            return n

    def add(self, topid, idlist):
        """create a node with id=topid (if needed), then add
        child nodes, one per entry in idlist
        """
        self._getnode(topid).link(*(self._getnode(i) for i in idlist))

测试一下

下面是如何使用上面定义的Tree类来解决指定的问题：

^{pr2}$

漫谈

这是一个经典的CS-chestnut，在现代编码教程中似乎没有太多的曝光（我认为，因为以前用树来解决的许多问题现在有了更简单的哈希表/基于dict的答案）。在

Answer 3

使用类似邻接表的数据结构将此问题表示为有向图。按照你的假设，3管理0和1。在

图形={4:[2，3]，2:[0]，3:[0，1]}

使用深度优先搜索（DFS）或呼吸优先搜索（BFS）遍历列出在某人下面报告的人员。在

DFS（图[2]）应返回0

DFS（图[4]）应返回0、2、1、3

返回[bf0，bf3]的值