python - 在多路树或连通图中查找一组元素/节点的根元素

Question

我找不到合适的算法来实现以下内容:

我有一组连接为连接图或多路树的 wifi 链接。

我遇到的问题是:当我断开连接时，几个 wifi 节点出现故障，我想知道根本问题是什么，即承载所有其他链接的 wifi 节点

例子:

• 节点1 -> 节点2、节点3和节点4
• 节点2->节点A、B、C
• 节点 3 是叶子
• 节点 4 -> 节点 D 和 E

如果我有节点 4、D 和 E 宕机，那么我知道根本原因是节点 4

我考虑过使用最不常见的祖先，但是，我无法将其适应多路树而不是二叉树

关于如何解决这个问题有什么建议吗？

Answer 1

你可以用一个字典来代表你的wifi网络，然后简单的使用递归来寻找问题的根源:

d = {1: [2, 3, 4], 2: ['A', 'B', 'C'], 3: None, 4: ['D', 'E']}
def search(_d, a):
   return (_d and a in _d) or (_d and any(search(d.get(i, []), a) for i in _d))

down = ['D', 'E', 4]
r = [a for i, a in enumerate(down) if all(search(d.get(a, []), j) for j in down[:i]+down[i+1:])]

输出:

[4]

编辑:如果中断的发起者可能不在 down 中，您可以简单地展平结构并再次运行搜索:

down = ['D', 'E']
_r = {a for c, _d in d.items() for a in [c, *([] if _d is None else _d)]}
result = [i for i in _r if all(search(d.get(i, []), j) for j in down)]

输出:

[1, 4]

输出是 [1, 4]，因为 4 是 1 的 child ，而 4包含受影响的子节点。这取决于您如何区分这些结果，因为两者都可能有效，即 1 可能已关闭或 4 可能已关闭。

---

根据您的最新意见，我认为最好的方法是创建一个新字典，为一个集合中的每个父节点记录所有子节点。

from collections import defaultdict
def get_paths(_d, c = []):
   for i in _d:
     if d.get(i) is None:
        yield c+[i]
     else:
        yield from get_paths(d[i], c+[i, *([] if d[i] is None else d[i])])

result = defaultdict(list)
for a, b in d.items():
   result[a].extend(([] if b is None else get_paths(b)))

result = {a:{i for c in b for i in c} for a, b in result.items()}

现在，获取故障节点:

def get_down(down):
   _r, _n = zip(*[[a, b] for a, b in result.items() if b and all(i in down for i in b)])
   n = {i for b in _n for i in b}
   return list(_r) + [i for i in down if i not in result and i not in n]


final_results = [get_down(i) for i in [['D', 'E','C'], ['D', 'E']]]

输出:

[[4, 'C'], [4]]