如何在好友关系无向图中查找三人好友三角结构

核心思路 #

为了避免重复统计同一个三角组合，我们按索引大小约束i < j < k遍历所有三元组，只要满足三个两两位置的邻接矩阵值均为1，就是符合要求的三人好友三角。这种方式不会出现重复计数的问题，也不需要额外做去重处理。

实现代码 #

可直接复用你已经生成的邻接矩阵matrix和姓名映射列表H运行：

triangles = []
user_count = len(H) # 总人数

# 遍历所有不重复的三元组 i < j < k
for i in range(user_count):
    for j in range(i + 1, user_count):
        # i和j不是好友直接跳过，减少无效遍历
        if matrix[i][j] != 1:
            continue
        for k in range(j + 1, user_count):
            # 校验剩余两组好友关系
            if matrix[j][k] == 1 and matrix[i][k] == 1:
                # 映射回真实姓名存入结果
                triangles.append((H[i], H[j], H[k]))

# 打印输出结果
print("所有好友三角如下：")
for tri in triangles:
    print(" - ".join(tri))

示例运行结果 #

对应你给出的测试用例，输出如下：

所有好友三角如下：
ivana - luka - mirjana
janko - mirko - slavko

如果你的使用场景总人数非常多，可以改用邻接表存储好友关系进一步优化遍历效率，普通场景下上述代码足够简单稳定，不容易出逻辑问题。

内容的提问来源于stack exchange，提问作者randommikrovalna