图(graph)
图和树的最大区别在于图的下一个节点可能指向已访问过的节点。因此在使用BFS及DFS遍历时,应维护一个Set,Set中存放已被访问过的节点,在遍历时先判断节点未被访问过再遍历即可。
//使用Queue实现BFS
public void BFSWithQueue(Node root) {
Queue<Node> queue = new LinkedList<>();
if (root != null)
queue.add(root);
Set<Node> visited = new HashSet<>();
while (!queue.isEmpty()) {
Node node = queue.poll();
visited.add(node);
//在这里处理遍历到的Node节点
if (node.children != null) {
for (Node child : node.children) {
if (child != null && !visited.contains(child){
queue.add(child);
}
}
}
}
}