用於派系發現的Bron Kerbosh算法 - 當樞軸頂點不存在時會發生什麼？

Question

上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工會X是空的情況還不清楚。由於u是未定義的，該函數是否繼續N（u）作爲空集（即它繼續爲P中的每個頂點v），還是返回給調用者？

Answer 1

當且僅當P和X都爲空時，union X爲空。這種情況在行中檢查

if P and X are both empty: 

因此，如果這種情況失敗，這意味着P或X或兩者都不是空的。因此，P union X中至少有一個元素。

換句話說：如果P union X爲空，我們report R as a maximal clique。

Answer 2

無論我們爲u的值選擇什麼。你的假設是P union X是空的，這意味着P和X都是空的。因此，我們暫且忽略u的值，然後轉到下一行「for each vertex v in P \ N(u):」。由於P爲空，因此P \ N(u)仍然爲空。因此無論如何，for循環都會被跳過。所以如果它讓你感覺好一些，你可以在那裏放一個return語句，但是正如它現在寫的那樣，它仍然會停止執行算法。