利用图和顶点查找团

2024-03-29 10:42:45 发布

您现在位置:Python中文网/ 问答频道 /正文

仅限PYTHON

我有一张图表

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]]

函数团(图、顶点)应采用邻接矩阵 图的表示形式、一个或多个顶点的列表,如果顶点创建团,则返回布尔值True (每个人都是其他人的朋友),否则返回False

 `def clique(graph, vertices)` 

我想知道上图中是否存在派系

如果是,则输出应为真,否则为假

例如,“集团”(图[2,3,4]),正确)

需要解释,谢谢


Tags: 函数falsetrue列表def图表朋友形式
1条回答
网友
1楼 · 发布于 2024-03-29 10:42:45

https://en.wikipedia.org/wiki/Clique_problem

在这里,根据您实际想要解决的问题,您可以找到一个算法的起点

图是否为团:只需检查所有节点是否彼此相邻即可

它是否包含一个集团?如果图形非空,则始终为true,因为单个顶点已经是大小为1的团

它是否包含大小为k的集团?蛮力

找到一个最大的集团?贪婪算法可能如链接中所述

找到所有最大派系?参考资料请参见维基百科页面(这很难)

相关问题 更多 >