如何使用Boost圖庫在廣度優先搜索期間訪問祖先頂點？

Question

我試圖使用Boost圖庫中包含的廣度優先搜索算法編寫我自己的連接組件發現版本，並且需要訪問祖先（導致發現當前頂點的頂點）頂點通過訪問者的discover_vertex回調來設置當前頂點的組件號。 任何方式可以輕鬆完成？

Answer 1

創建一個用於記錄正在檢查的頂點（從隊列中彈出）的examine_vertex回調函數。這個頂點將是任何頂點被發現的祖先。

從BGL的BFS documentation的僞代碼：

vis.examine_vertex（U，G）在各頂點，因爲它是從 隊列中刪除調用 。

BFS(G, s) 
    for each vertex u in V[G] 
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
    end for 
    color[s] := GRAY 
    d[s] := 0 
    ENQUEUE(Q, s) 
    while (Q != Ø) 
    u := DEQUEUE(Q)     # `u` is recorded in examine_vertex callback 
    for each vertex v in Adj[u] 
     if (color[v] = WHITE) 
     color[v] := GRAY 
     d[v] := d[u] + 1 
     p[v] := u 
     ENQUEUE(Q, v)     # `v` is discovered, `u` is its ancestor. 
     else 
     if (color[v] = GRAY) 
      ... 
     else 
      ... 
    end for 
    color[u] := BLACK 
    end while 
    return (d, p)