Python3 朋友的朋友

Question

我正在开发此功能以寻找两个人之间可能的友谊。友谊系统以传递方式工作，也就是说，如果 A 是 B 的朋友，B 是 C 的朋友，那么 A 也是 C 的朋友。字典存储初始关系（如图形）和函数参数是字典和你想识别他们是否是朋友的两个人的名字。

def findfriendship(people, X, Y):
    if Y in people[X] or X in people[Y]:
        return True

    if len(people[X]) != 0:
        for friend in people[X]:
            return findfriendship(people, friend, Y)

    if len(people[Y]) != 0:
        for friend in people[Y]:
            return findfriendship(people, X, friend)

    return False

这是我的代码，我成功地确定了两个人之间可能存在的友谊，只要其中一个人的朋友列表不为空，就像这样：

friendships = {'Jordan': ['Shaq'], 'Lebron': [], 'Kobe': [], 'Shaq': ['KD'], 'KD': []}
print(findfriendship(friendships, 'KD', 'Jordan')) -> return True

但是我无法解决双方都没有直接朋友的问题，像这样：

friendships = {'Jordan': ['Shaq'], 'Lebron': [], 'Kobe': ['KD', 'Lebron'], 'Shaq': ['KD'], 'KD': []}
print(findfriendship(friendships, 'Lebron', 'KD')) -> return False

是returns假的，但是科比是他们俩的朋友，所以他们应该是朋友。

你们能帮我解决这个问题吗？或者你们知道类似的问题以便我理解这种概念吗？感谢您的关注。

Answer 1

如果我们可以获得任何一个人的完整朋友列表，那么检查两个人是否是朋友会很容易。让我们为此编写一个帮助程序：

friendships = {
    'Jordan': ['Shaq'], 'Lebron': [],
    'Kobe': ['KD', 'Lebron'], 'Shaq': ['KD'], 'KD': [],
    "foo": ["bar", "baz"], "bar": [], "baz":[],
}

def buildFriendSet (x, people=None, fSet=None):
    people = people or friendships;       # default value
    fSet = fSet or set([x] + people[x]);  # Friend Set
    changeDetected = False;
    for kPerson, vPersonList in people.items():
        personList = [kPerson] + vPersonList;
        if fSet.issuperset(personList):
            pass;
        elif fSet.intersection(personList):
            fSet = fSet.union(personList);
            changeDetected = True;
    if not changeDetected:
        return fSet;
    return buildFriendSet(x, people, fSet);

print(buildFriendSet('KD'));
# Output: {'Shaq', 'Kobe', 'KD', 'Lebron', 'Jordan'}

print(buildFriendSet('foo'))
# Output: {'baz', 'bar', 'foo'}

一旦我们可以计算出任何人的朋友集，检查两个人是否是朋友就很容易了：

def checkFriends (x, y, people=None):
    people = people or friendships; # default value
    return (x in people[y] or y in people[x] or
        x in buildFriendSet(y, people)
    );

print(checkFriends('KD', 'Jordan')); # -> True
print(checkFriends('Lebron', 'KD')); # -> True
print(checkFriends('KD', 'foo'));    # -> False

buildFriendSet()背后的逻辑：

我们遍历 people 并检查朋友集 fSet 是否发生变化。如果没有检测到变化，那么我们 return fSet 不变。否则，我们继续寻找更多的朋友。

对于给定的密友群组，例如上面的任何 personList，如果群组中的每个人都已经在 fSet 中，则无需更改 fSet。这对应于 .issuperset(.) 检查。

否则，如果personList中至少有一个人已经在fSet中，那么通过联想，其他人也必须在其中！我们分别使用 .intersection(.) 和 .union() 来检查和实现。

每个人都是自己的朋友吗？

以上实现假定每个人都是自己的朋友。如果不需要这种行为，使用简单的 if-guard and/or fSet.remove(.) 就足够了。

Python3 朋友的朋友

Python3 Friend of a Friend

python

depth-first-search