如何遍歷基於兩個邊緣之間的角度的圖形

Question

我困在基於兩個邊緣之間的角度的圖形遍歷的問題中。我想如下總結的問題，給出5個頂點a,b,c,d,e和邊緣(a, b)，(b, c)，(c, d)，(d, e)。

如果我想遍歷基於計算兩個邊緣之間的角度例如像angle((a, b), (b, c))的曲線圖。如果我的角度大於10度，我應該停在b並重新開始這個過程。

我需要考慮哪些步驟來處理具有具體編程結構的問題。

Answer 1

如果我理解正確的，當angle((a,b),(b,c))返回的值超過某個閾值（10，在你的例子），你應該停止遍歷圖。

這意味着該節點（b）實際上並沒有通過連接兩條邊（(a,b)和(b,c)）來提供幫助。它可能對其他一些邊緣有用，但該特定連接不可用。

我建議交換邊和節點的角色。在G每邊成爲G'在G'只有一個節點，並在G成爲每個節點和邊緣如果angle()值返回比你的閾值低的值。

在G'你現在可以運行BFS，DFS或者您喜歡的任何其他算法。完成後，使用相反轉換將您的答案「翻譯」回有問題的原始圖形。