检查 2 个人是否通过朋友连接

Question

每个子列表都意味着他们是朋友，现在我想创建一个函数def is_connected_via_friendships_with来检查他们是否通过与另一个人的友谊联系在一起。例如，玛丽是卢卡斯的朋友。她是彼得的朋友，彼得是朱莉的朋友。因此，该函数需要为玛丽和朱莉返回True。另请注意，我不能为此使用import。提前谢谢你。

network = {'friendships' :[['Marie', 'Lucas'], ['Lucas', 'Patsy'], ['Emma', 'Lucas'], ['Emma', 'Kevin'], ['Peter', 'Emma'], ['Peter', 'Lucas'], ['Peter', 'Julie'], ['Suzy', 'Tobias']]}
print (is_connected_via_friendships_with(network, 'Marie', 'Julie')) # true
print (is_connected_via_friendships_with(network, 'Julie', 'Tobias')) # false
print (is_connected_via_friendships_with(network, 'Julie', 'Frank'))  # false

Answer 1

你基本上必须找到两个朋友是否位于图形的相同连接组件中。多种方法检查 2 个节点是否位于同一连接的组件中。您可以使用不相交集来优化此问题的实现。从这里使用的不相交集实现

守则如下：

class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent
def find(self, item):
if self.parent[item] == item:
return item
else:
return self.find(self.parent[item])
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
def is_in_same_set(self, fa, fb):
return self.find(fb) == self.find(fa)
def get_vertices(network):
myset = set()
for a,b in network['friendships']:
myset.add(a)
myset.add(b)
return list(myset)

def is_connected_via_friendships_with(network, fa,fb):
return network.is_in_same_set(fa,fb)
def main():
network = {'friendships' :[['Marie', 'Lucas'], ['Lucas', 'Patsy'], ['Emma','Lucas'], ['Emma', 'Kevin'], ['Peter', 'Emma'], ['Peter', 'Lucas'], ['Peter', 'Julie'],     ['Suzy', 'Tobias']]}
vertices = get_vertices(network)
parent = {}
for v in vertices:
parent[v] = v
ds = DisjointSet(vertices, parent)
for a,b in network['friendships']:
ds.union(a,b)
print(is_connected_via_friendships_with(ds, 'Marie', 'Julie'))
print(is_connected_via_friendships_with(ds, 'Peter', 'Suzy'))
main()

输出为：

真
假

Answer 2

这是一个经典的连接组件问题。由于友谊是双向的，因此将子列表列表转换为一组可哈希冻结集作为候选池会更有效，以便对于每个起始顶点，您可以通过遍历冻结集集中的候选来找到连接的组件，以找到与当前组件集相交的冻结集并将其从候选池中删除， 直到池中没有更多的候选人：

pool = set(map(frozenset, network['friendships']))
groups = []
while pool:
groups.append(set(pool.pop()))
while True:
for candidate in pool:
if groups[-1] & candidate:
groups[-1] |= candidate
pool.remove(candidate)
break
else:
break

groups会变成：

[{'Patsy', 'Emma', 'Peter', 'Marie', 'Julie', 'Kevin', 'Lucas'}, {'Suzy', 'Tobias'}]

然后，将集合列表转换为集合字典是微不足道的，每个名称作为高效查找的关键：

connected = {name: group for group in groups for name in group}
def is_connected_via_friendships_with(name1, name2):
return name2 in connected.get(name1, ())

因此：

print(is_connected_via_friendships_with('Marie', 'Julie'))
print(is_connected_via_friendships_with('Julie', 'Tobias'))
print(is_connected_via_friendships_with('Julie', 'Frank'))

输出：

True
False
False