我正在嘗試使用隊列來實現BFS算法,並且我不想查找任何用於學習目的的在線代碼。我所做的只是遵循算法並嘗試實現它。我有一個關於鄰接矩陣的問題(圖的數據結構)。我是否必須使用BFS實現Adjacency矩陣?
我知道一個共同的圖數據結構是鄰接矩陣。所以,我的問題在這裏,我是否必須與BFS算法一起實現Adjacency矩陣,或者沒關係。
我真的很困惑。 讓我困惑的事情之一是圖表的數據,如果沒有數據結構,這些數據應該存儲在哪裏?
真誠
我正在嘗試使用隊列來實現BFS算法,並且我不想查找任何用於學習目的的在線代碼。我所做的只是遵循算法並嘗試實現它。我有一個關於鄰接矩陣的問題(圖的數據結構)。我是否必須使用BFS實現Adjacency矩陣?
我知道一個共同的圖數據結構是鄰接矩陣。所以,我的問題在這裏,我是否必須與BFS算法一起實現Adjacency矩陣,或者沒關係。
我真的很困惑。 讓我困惑的事情之一是圖表的數據,如果沒有數據結構,這些數據應該存儲在哪裏?
真誠
選擇數據結構的最佳方式是根據操作。在手操作的完整列表,評估實現WRT標準的問題非常重要:空間,速度,代碼大小等
對於BFS,操作也很簡單:
Set<Node> getSources(Graph graph) // all in graph with no in-edges
Set<Node> getNeighbors(Node node) // all reachable from node by out-edges
現在我們可以評估圖數據中的n項結構選項=節點的數量:
的聰明只是保持設定爲圖形構成的源極,所以成本是由邊緣插入攤銷。也就是說,當你創建一個節點時,將它添加到源列表中,因爲它沒有出邊。在添加邊時,請從源集中移除前端節點。
現在您可以根據運行時間作出明智的選擇。在空間,簡單性或任何其他考慮因素的作用下也是如此。然後選擇並執行。
廣度優先搜索假設你有某種形式的代表,你有工作,其效率取決於你有代表性的選擇的圖形結構的方式,但是你就不會被限制使用鄰接矩陣。 BFS的許多實現都以某種方式隱式表示圖形(例如,作爲存儲迷宮的二維數組或某種形式的遊戲)並且工作得很好。您也可以使用一個鄰接表,這對我們在BFS中特別有效。
您將要編寫的特定代碼將取決於圖表的表示方式,但不要拘泥於這種方式。選擇最簡單的應用程序。
嘗試鄰接列表... – Mehrdad
「pop_back」的返回類型是「void」。 – emlai
而不是編輯你的問題,問一些根本不同的東西,然後不接受答案,我建議在這裏問一個全新的問題。 – templatetypedef