烟台网站制作厂家联系方式,网站几个数据库,莱芜市网站建设公司,文老师网络规划设计师图常见的遍历方式有两种#xff0c;一种是宽度优先遍历#xff0c;一种是深度优先遍历。
宽度优先遍历 宽度优先遍历和之前介绍的二叉树的层级遍历类似#xff0c;主要也是利用Queue来完成层级的遍历#xff0c;除此之外#xff0c;因为图中很可能有环#xff0c;所以还…图常见的遍历方式有两种一种是宽度优先遍历一种是深度优先遍历。
宽度优先遍历 宽度优先遍历和之前介绍的二叉树的层级遍历类似主要也是利用Queue来完成层级的遍历除此之外因为图中很可能有环所以还需要一个Set集合来保证遍历的过程中没有重复的点打印防止死循环。 比如说图形结构如下图所示 遍历时先遍历a将a放入队列弹出后a直接到达的节点的有b和c将b,c放入队列b弹出时直接到达的节点有c和p。 如果此时再将c放入队列那c就会遍历两次根据set集合判断放入p遍历完c,p后p直接到达的点是a如果没有set集合那么就死循环了。在a处重新开始遍历。
BFS 需要注意的是一定要给一个开始的节点node。并且出堆就打印。
public class BFS {public static void bfs(Node node) {if (node null) {return;}QueueNode heap new LinkedList();SetNode set new HashSet();heap.add(node);set.add(node);while (!heap.isEmpty()) {Node cur heap.poll();System.out.print(cur.value );for (Node next : cur.nexts) {if (!set.contains(next)) {heap.add(next);set.add(next);}}}}
}深度优先遍历 深度优先遍历的技巧就在于一条道走到黑只要下面还有就一直先向下找同样需要set集合来去重避免死循环。进栈就打印。
DFS
内层for循环中与BFS有所区别利用set去重做判断如果不存在则将当前Node和next的Node都放入Stack中然后break。注意要先将当前Node放入栈中因为后进先出都放入后栈中会保留你遍历的路径break再次弹出的是第一次放入的next的Node。下次会从next的Node向下遍历看是否在set中存在。
public class DFS {public static void dfs(Node node){if (node null){return;}StackNode stack new Stack();SetNode set new HashSet();stack.add(node);set.add(node);System.out.println(node.value );while (!stack.isEmpty()){Node cur stack.pop();for (Node next : cur.nexts){if (!set.contains(next)){stack.add(cur);stack.add(next);set.add(next);System.out.println(next.value );break;}}}}
}
