在多路树或连通图中查找一组 elements/nodes 的根元素

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 的子节点，而 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]]

在多路树或连通图中查找一组 elements/nodes 的根元素

Finding the root elements of a set of elements/nodes in a multiway tree or a connected graph

python

algorithm

graph-theory

linked-list