我找不到合适的算法来实现以下内容:
我有一组连接为连接图或多路树的 wifi 链接。
我遇到的问题是:当我断开连接时,几个 wifi 节点出现故障,我想知道根本问题是什么,即承载所有其他链接的 wifi 节点
例子:
- 节点1 -> 节点2、节点3和节点4
- 节点2->节点A、B、C
- 节点 3 是叶子
- 节点 4 -> 节点 D 和 E
如果我有节点 4、D 和 E 宕机,那么我知道根本原因是节点 4
我考虑过使用最不常见的祖先,但是,我无法将其适应多路树而不是二叉树
关于如何解决这个问题有什么建议吗?
最佳答案
你可以用一个字典来代表你的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]]
关于python - 在多路树或连通图中查找一组元素/节点的根元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57850272/