Java一種面向對象的編程語言,廣泛應用于網絡通訊、企業信息化、游戲等領域。在開發過程中,深度遍歷和廣度遍歷算法是非常常用的算法。
下面分別介紹Java深度遍歷和廣度遍歷的代碼實現。
Java深度遍歷
public void DFS(Node node) { if(node == null) { return; } System.out.print(node + " "); // 先訪問根節點 node.visited = true; for(Node neighbor: node.neighbors) { if(!neighbor.visited) { DFS(neighbor); //遞歸遍歷鄰居節點 } } }
深度遍歷算法采用遞歸調用的方式遍歷整個圖,對于每一個起點進行遍歷,如果當前節點未被訪問,則將其標記為已訪問,并繼續遞歸遍歷當前節點的所有鄰居節點。
Java廣度遍歷
public void BFS(Node node) { Queuequeue= new LinkedList<>(); queue.add(node); node.visited = true; while(!queue.isEmpty()) { Node current = queue.remove(); System.out.print(current + " "); // visit the node for(Node neighbor: current.neighbors) { if(!neighbor.visited) { neighbor.visited = true; queue.add(neighbor); } } } }
廣度遍歷算法采用隊列的方式遍歷整個圖,從起點開始遍歷,首先遍歷當前節點的所有鄰居節點,并標記為已訪問,將鄰居節點加入隊列中,依次遍歷隊列中剩余的節點。
通過深度遍歷和廣度遍歷兩種算法的實現,可以很方便地實現圖的遍歷。
上一篇python畫鋼鐵俠
下一篇python界面文字亂碼