如何通过删除节点将有向图转换为完全有向图并保留最多节点？

首先得明确咱们要啥：从给定的有向图里挑出最多的节点，让这些节点构成题目说的完全有向图——简单说就是挑出来的节点里，任意两个节点之间必须有双向的边，而且每个节点自己得有自环，反映在邻接矩阵上就是，这些节点对应的子矩阵里全是1，没一个0。

第一步：先筛掉没自环的节点 #

先把所有没有自环的节点直接排除（也就是邻接矩阵里对角线位置A[i][i] = 0的节点i），剩下的叫候选集合C。为啥？因为题目要求的完全有向图每个节点必须有自环，没自环的根本没法留，直接pass就行。

第二步：转成无向图找最大团 #

接下来把问题简化：基于候选集合C，建一个无向图G'：

• 节点就是候选集里的那些节点
• 对于两个不同的节点u和v，只有当原邻接矩阵里A[u][v]和A[v][u]都是1的时候，才在G'里给这俩节点连一条无向边。

这一步的关键是，把有向图里“双向边都存在”的要求，转换成无向图里“两个节点相连”的问题。这时候咱们要找的最大节点子集，就对应这个无向图里的最大团——最大团里任意两个节点都相连，放到原有的向图里就是双向边都存在，再加上第一步筛过的节点都有自环，正好符合题目要求的完全有向图。

第三步：求解最大团 #

怎么找最大团看节点数量来选方法：

• 如果节点少（比如n≤20）：用回溯法或者分支限界法，能精准找到最大的团。回溯法的思路就是挨个试节点，每次加新节点的时候看看它和当前团里的所有节点都连边不，要是都连就加进去继续递归，不然就跳过，过程中记着最大的那个团就行。
• 如果节点多：精确求解太慢，就用贪心算法凑个近似解——比如每次选度数最高的节点加入团，然后把这个节点和它不相连的节点都删掉，重复直到没节点；或者用模拟退火、遗传算法这类启发式方法找个规模大的团。

第四步：输出结果 #

找到最大的团之后，把对应的节点集合输出就完事了。要是有好几个规模一样的最大团，随便输出一个或者全输出都行。

假设邻接矩阵是这样的（节点0到3）：

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

第一步：所有节点对角线都是1，候选集C = {0,1,2,3}。
第二步：建无向图：

• 0和1双向边都有，连边；
• 0和2没双向边，不连；
• 0和3双向边都有，连边；
• 1和2双向边都有，连边；
• 1和3没双向边，不连；
• 2和3双向边都有，连边；
  无向图的边就是(0,1)、(0,3)、(1,2)、(2,3)。
  第三步：找最大团，这里最大的团都是2个节点的，比如{0,1}、{0,3}这些，随便输出一个就行。

• 最大团问题是NP难问题，节点多的时候精确求解会很慢，这时候就得权衡是要精准还是要速度，选合适的方法。
• 要是原邻接矩阵里有个节点，和所有有自环的节点都有双向边，那这个节点加所有符合条件的节点就是最大的子集。

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