1

ピボットを使用した BK クリーク検出に関するウィキペディアの疑似コード:

   BronKerbosch2(R,P,X):
   if P and X are both empty:
       report R as a maximal clique
   choose a pivot vertex u in P ⋃ X
   for each vertex v in P \ N(u):
       BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

P union X が空であるとどうなるかは不明です。u は定義されていないので、関数は N(u) を空集合として続行しますか (つまり、P の頂点 v ごとに続行します)、それとも呼び出し元に戻りますか?

4

2 に答える 2

2

P 共用体 X は、P と X の両方が空の場合にのみ空です。この条件は行でチェックされます

if P and X are both empty:

したがって、この条件が満たされない場合、これは P または X またはその両方が空でないことを意味します。したがって、P 結合 X には少なくとも 1 つの要素がなければなりません。

言い換えれば、P union X が空の場合、 we report R as a maximal clique.

于 2011-09-12T15:55:55.937 に答える