深度優先和廣度優先是遍歷圖的兩種常見方法。
圖遍歷是只訪問圖中每個頂點一次的過程。有兩種流行的遍歷圖的方法：深度優先遍歷（或深度優先搜尋）和廣度優先遍歷（或廣度-先搜尋）。兩次遍歷都會產生生成樹，可以使用類別對其進行建模，如下圖所示。請注意，Tree 是在 AbstractGraph 類別中定義的內部類別。 AbstractGraph.Tree 與搜尋元素中定義的 Tree 介面不同。 AbstractGraph.Tree 是一個專門的類，用於描述節點的父子關係，而 Tree 介面定義了樹中的搜尋、插入和刪除等常見操作。由於不需要對生成樹執行這些操作，因此 AbstractGraph.Tree 未定義為 Tree.
Tree 類別在 AbstractGraph.java 中第 226-293 行的 AbstractGraph 類別中被定義為內部類別。建構函式建立一棵具有根、邊和搜尋順序的樹。
Tree 類別定義了七個方法。 getRoot() 方法傳回樹的根。您可以透過呼叫 getSearchOrder() 方法來取得搜尋頂點的順序。您可以呼叫 getParent(v) 在搜尋中尋找頂點 v 的父節點。呼叫 getNumberOfVerticesFound() 傳回搜尋到的頂點數。方法 getPath(index) 傳回從指定頂點索引到根的頂點清單。呼叫 printPath(v) 顯示從根到 v 的路徑。您可以使用 printTree() 方法顯示樹內的所有邊。
以上是圖表遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章！
