高效地擴展圖形邊緣集合

Question

我從圖形中有一組邊緣，並且想要用與任何邊緣共享一個頂點的所有邊緣來擴展它。我怎樣纔能有效地與boost::graph s？

我能夠想出的唯一方法是提取所有源和目標頂點的天真解決方案，使用boost::adjacent_vertices獲取所有鄰接點，然後使用boost::edge創建所有新邊緣。有沒有更好的方法來做到這一點？

上下文：圖頂點是地形三角剖分的質心，邊連接相應三角形相鄰的頂點（如此類的雙圖）。我期望擴展的邊集合對應於被阻止的三角形間路徑，並且阻塞區域正在擴大。這個區域是圓形的，所以我會用上面的天真方法看到的大部分邊緣都將成爲該組的一部分。

Answer 1

不用考慮每個步驟中所有相鄰的頂點來生成新邊，而是使用屬性圖來標記已經遇到的邊。因此，您只需要考慮每一步中未標記的邊。在將所有邊緣事件添加到您的集合後，標記頂點。

鑑於boost :: graph使用的內部數據結構是一個鄰接列表或一個鄰接矩陣，我不認爲有任何進一步的改進是可能的。