基于矩阵乘法的无向图三角形检测：新增顶点输出功能需求

我有一段用矩阵乘法计算无向图三角形数量的代码，现在想优化它，让它能输出构成三角形的顶点。可以用numpy、networkx等第三方库，但必须基于矩阵乘法实现（已知暴力法可行，但不采用）。

示例说明 #

邻接矩阵示例 #

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

对应边列表 #

x,y
0,1
1,2
1,3
2,3

该图中存在由顶点1、2、3构成的三角形，需要程序将其输出到控制台。

原代码（仅输出三角形数量） #

# 顶点数量
V = 4
# 由邻接矩阵表示的图
graph = [[0, 1, 0, 0],
         [1, 0, 1, 1],
         [0, 1, 0, 1],
         [0, 1, 1, 0]]

# 将顶点存入字典
vertexes = {}
for i in range(len(graph)):
    vertexes[i] = i

print(vertexes)
## >> {0: 0, 1: 1, 2: 2, 3: 3}

# 矩阵乘法函数
def multiply(A, B, C):
    global V
    for i in range(V):
        for j in range(V):
            C[i][j] = 0
            for k in range(V):
                C[i][j] += A[i][k] * B[k][j]


# 计算矩阵迹的工具函数（对角线元素之和）
def getTrace(graph):
    global V
    trace = 0
    for i in range(V):
        trace += graph[i][i]
    return trace


# 计算图中三角形数量的工具函数
def triangleInGraph(graph):
    global V

    # 存储graph^2的矩阵
    aux2 = [[None] * V for _ in range(V)]

    # 存储graph^3的矩阵
    aux3 = [[None] * V for i in range(V)]

    # 初始化辅助矩阵为0
    for i in range(V):
        for j in range(V):
            aux2[i][j] = aux3[i][j] = 0

    # 计算得到aux2为graph的平方
    multiply(graph, graph, aux2)

    # 计算得到aux3为graph的立方
    multiply(graph, aux2, aux3)

    trace = getTrace(aux3)
    return trace // 6


print("图中三角形总数：", triangleInGraph(graph))
## >> 图中三角形总数： 1

优化后的代码（输出三角形顶点） #

借助numpy简化矩阵运算，基于矩阵乘法逻辑提取三角形顶点：

import numpy as np

# 邻接矩阵
graph = [[0, 1, 0, 0],
         [1, 0, 1, 1],
         [0, 1, 0, 1],
         [0, 1, 1, 0]]
G = np.array(graph)
V = G.shape[0]

# 计算邻接矩阵的平方
G2 = G @ G

# 计算G与G2的逐元素乘积，M[i][j]表示i和j有直接边且存在长度为2的路径
M = G * G2

# 存储去重后的三角形
triangles = set()

# 遍历上三角区域（i < j），避免重复统计
for i in range(V):
    for j in range(i+1, V):
        if M[i][j] > 0:
            # 找到所有满足条件的中间顶点k
            ks = np.where((G[i] == 1) & (G[:, j] == 1))[0]
            for k in ks:
                # 排序后存入集合，消除重复的三角形表示
                triangle = tuple(sorted((i, j, k)))
                triangles.add(triangle)

# 输出结果
print("图中的三角形：")
for tri in triangles:
    print(f"顶点{tri[0]}、{tri[1]}、{tri[2]}")
print(f"三角形总数：{len(triangles)}")

代码逻辑说明 #

1. 矩阵乘法核心：邻接矩阵的平方G2[i][j]代表从顶点i到j的长度为2的路径数量。当G[i][j] == 1（i和j直接相连）且G2[i][j] > 0时，说明存在中间顶点k，使得i-k-j构成路径，进而i、j、k可能形成三角形。
2. 去重处理：通过遍历上三角矩阵（i < j），并对三角形顶点排序后存入集合，避免同一个三角形被多次计数（无向图中每个三角形会被6次重复统计）。
3. 高效运算：使用numpy的矩阵运算替代手动实现，大幅提升代码简洁性和运行效率。

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