Bron-Kerbosch算法的迭代版本？

Bron–Kerbosch algorithm是列出圖的所有極大集合的方法。我最近成功實現了算法，只是爲了好玩。缺點是算法是遞歸的，因此只能在小圖上運行，直到堆棧溢出。Bron-Kerbosch算法的迭代版本？

應該可以使算法純粹迭代。考慮維基百科上的基本版本（不支持）。算法的迭代版本如何在僞代碼中看起來像？有什麼地方有說明嗎？

我想像一個堆棧數據結構來模擬遞歸。我也應該有一個循環來測試P和X的空白，但是我沒有看到完整的答案。

2015-02-09 Gideon

因此，這是一個有效的問題，但IIRC B- -K在堆棧的最大深度中需要時間指數。 – 2015-02-09 13:00:35

The recursive version is given in Wikipedia就象這樣：

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

爲了模擬遞歸，我們只需要使用堆棧跟蹤三個變量：

BronKerbosch(P): 
    S := empty stack 
    S.push({}, P, {}) 
    while S is not empty: 
     R, P, X := S.pop() 
     if P and X are both empty: 
      report R as a maximal clique    
     if P is not empty: 
      v := some vertex in P 
      S.push(R, P \ {v}, X ⋃ {v}) 
      S.push(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))

來源

2015-02-11 20:50:22

Bron-Kerbosch算法的迭代版本？

回答

相關問題