Java是一個高效、可靠的編程語言,它有著廣泛的應用領域。其中,廣度和深度遍歷是Java語言中非常重要的算法。
廣度遍歷又稱為寬度優先遍歷,是一種基于隊列實現的算法。它的策略是先訪問一個節點的所有相鄰節點,然后再訪問這些相鄰節點的相鄰節點,以此類推,直到遍歷結束。它一般用于解決最短路徑和連通塊問題,比如在搜索引擎中查找最短路徑。
public void breadthFirstSearch(Node root) { Queuequeue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { Node node = queue.poll(); if (node != null) { visit(node); for (Node adjNode : node.getAdjNodes()) { if (!adjNode.isVisited()) { adjNode.setVisited(true); queue.add(adjNode); } } } } }
深度遍歷又稱為深度優先遍歷,是一種基于棧實現的算法。它的策略是先訪問一個節點,然后遞歸訪問這個節點的第一個未被訪問的相鄰節點,再返回遞歸點,訪問它的下一個未被訪問的相鄰節點,直到該節點沒有未被訪問的相鄰節點為止。
public void depthFirstSearch(Node root) { if (root == null) { return; } visit(root); root.setVisited(true); for (Node adjNode : root.getAdjNodes()) { if (!adjNode.isVisited()) { depthFirstSearch(adjNode); } } }
無論是廣度遍歷還是深度遍歷,都是很重要的算法,而Java語言恰好提供了隊列和棧等數據結構,方便我們實現這兩種遍歷算法。