如何在图形中找到“朋友三角”？

Question

我有朋友的名字，我正在寻找三角形的朋友，如果有的话。 示例（紧挨着的名字被归类为朋友，在第一行中，第一个数字表示人数，第二个数字表示友谊的数量）：

6 7
mirko slavko
slavko janko
janko mirko
slavko luka
luka mirjana
mirjana ivana
ivana luka

在这个例子中，扬科-米尔科-斯拉夫科是一个三角形，米尔贾纳-卢卡-伊凡纳是另一个三角形

我编写了一个代码，生成了一个表示这个图的2d列表

L = [input().split() for i in range (n)]
H=[]
for i in range(n):
    for j in range(2):
        if L[i][j] not in H:
            H.append(L[i][j])
H.sort()

for number, name in enumerate(H):
    for i in range (n):
        for j in range(2):
            L[i][j]=L[i][j].replace(name, str(number))
        
    
matrix = [[0 for i in range(m)] for j in range(m)]

for i, j in L:
    matrix[int(i)][int(j)]=matrix[int(j)][int(i)]=1

图表如下所示（姓名按字母顺序排列，每行和每列代表一个姓名，1表示存在友谊，0表示这两个人不是朋友）：

[0, 0, 1, 1, 0, 0]  
[0, 0, 0, 0, 1, 1]  
[1, 0, 0, 1, 0, 1]  
[1, 0, 1, 0, 0, 0]  
[0, 1, 0, 0, 0, 1]  
[0, 1, 1, 0, 1, 0]  

我的问题是如何用代码找到三角形

Answer 1

最简单的方法是

1. 创建一个字典，其键是人的名字，值是该人的朋友的集。确保如果A在B的朋友集中，B也在A的朋友集中

2. 对于每对人A和B，查看friends[A].intersect(friends[B])是否为空

Answer 2

大多数形式的clique problem是困难的，最一般的解是NP完全的。因此，假设输入表示是有效的，那么O（N**3）可能是你能做的最好的了，因为你已经制作了2d矩阵，你在这方面做得很好

friends = [
     [0,1,1,0],
     [1,0,1,1],
     [1,1,0,0],
     [0,1,0,0]]
n = 4

for i in range(n):
    for j in range(i+1, n):
        if not friends[i][j]:
            continue
        for k in range(j+1, n):
            if friends[i][k] and friends[j][k]:
                print('friends!')
                print(i,j,k)