Python实现Clique检测：判断指定顶点是否构成团

问题背景 #

我们需要实现一个Python函数clique(graph, vertices)，接收邻接矩阵表示的无向图，以及一个顶点列表，判断这些顶点是否构成团——也就是集合里任意两个不同的顶点之间都有直接相连的边。给定的示例图邻接矩阵为：

graph = [[0,1,1,1,0], [1,0,0,0,0], [0,1,0,1,1], [1,0,1,0,1], [0,0,1,1,0]]

同时需要验证类似[2,3,4]这样的顶点集合是否符合团的定义。

实现思路 #

团的核心要求是所有顶点两两相邻，所以我们只需要：

1. 遍历顶点列表中所有的两两组合（避免重复检查，只检查i < j的对）；
2. 对每一对顶点，检查邻接矩阵中对应的位置是否为1（无向图中graph[u][v]和graph[v][u]值相同，只需检查一个）；
3. 如果所有顶点对都满足相邻条件，返回True；只要有一对不相邻，立即返回False。

代码实现 #

def clique(graph, vertices):
    # 获取顶点列表的长度
    num_vertices = len(vertices)
    # 遍历所有两两组合
    for i in range(num_vertices):
        for j in range(i + 1, num_vertices):
            u = vertices[i]
            v = vertices[j]
            # 检查两个顶点是否有边相连
            if graph[u][v] != 1:
                return False
    # 所有顶点对都相邻，构成团
    return True

# 示例图
graph = [[0,1,1,1,0], [1,0,0,0,0], [0,1,0,1,1], [1,0,1,0,1], [0,0,1,1,0]]

测试与验证 #

验证[2,3,4]是否为团

运行以下代码：

print(clique(graph, [2,3,4]))  # 输出: True

为什么是True？我们逐个检查顶点对：

• 顶点2和3：graph[2][3] = 1（有边）；
• 顶点2和4：graph[2][4] = 1（有边）；
• 顶点3和4：graph[3][4] = 1（有边）；
  所有两两顶点都相邻，符合团的定义。

其他测试案例

• 测试[0,1,2]：顶点1和2之间graph[1][2] = 0（无边），返回False；
• 测试[0,2,3]：所有两两顶点都相邻，返回True。

额外优化（可选） #

如果需要处理非法顶点索引（比如输入的顶点超出邻接矩阵的范围），可以添加索引合法性检查：

def clique(graph, vertices):
    max_valid_index = len(graph) - 1
    # 检查每个顶点是否在合法范围内
    for v in vertices:
        if not (0 <= v <= max_valid_index):
            raise ValueError(f"顶点{v}超出图的合法索引范围（0到{max_valid_index}）")
    
    num_vertices = len(vertices)
    for i in range(num_vertices):
        for j in range(i + 1, num_vertices):
            u = vertices[i]
            v = vertices[j]
            if graph[u][v] != 1:
                return False
    return True

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