让我们核对一下号码。让
n个
是顶点的数目,
E类
边的数目。
0个三元组在o中(
n个
^三)
1个三合会在O(
E类
*
n个
)
2+3个三元组在o中(
E类
)
要获得2+3三元组:
For every node a:
For every neighbor of a b:
For every neighbor of b c:
if a and c are connected, [a b c] is a 3 triad
else [a b c] is a 2 triad
remove a from list of nodes (to avoid duplicate triads)
下一步取决于目标是什么。如果您只需要1和0个空间坐标轴,那么这就足够了:
说明:
1个三元组都是连通节点+1个非连通节点,因此我们通过计算连通节点+1个其他节点的个数得到这个数,并减去其他节点连通的情况(2和3个三元组)
0空间坐标轴只是节点的所有组合减去其他空间坐标轴。
如果你真的需要列出三元组,那你就太不走运了,因为不管你做什么,列出0个三元组都是在o(n^3)中的,一旦图变大,你就死定了。
上述2+3空间坐标的算法为o(e*max(neighbors)),其他部分为o(e+n),用于计算节点和边。比o(n^3)要好得多,o(n^3)需要明确列出0个三元组。列出1个triad仍然可以在o(e*n)中完成。