图的遍历

1.宽度优先遍历：

 1 /*
 2      * 图中关于点的宽度优先遍历(使用队列来进行实现)
 3      * 从一个点出发宽度优先遍历所有的点
 4      */
 5     
 6     public static void NodeBfs(Node node) {
 7         if (node == null) {
 8             return;
 9         }
10         Queue q = new LinkedList<>();
11         HashSet set = new HashSet<>();
12         q.add(node);
13         set.add(node);
14         while (q.size() > 0) {
15             Node t = q.poll();
16             System.out.print(t.val + " ");
17             for (Node next : t.nexts) {
18                 if (!set.contains(next)) {//处理回环问题,避免一个点被重复输出
19                     q.add(next);
20                     set.add(next);
21                 }
22             }
23         }
24     }

2，深度优先遍历：

 1 /*
 2      * 图中关于点的深度优先遍历(栈实现)
 3      */
 4     public static void NodeDfs(Node node) {
 5         if (node == null) {
 6             return;
 7         }
 8         Stack sk = new Stack<>();//深度优先遍历对应的数据结构即为栈
 9         HashSet set = new HashSet<>();
10         sk.add(node);
11         set.add(node);
12         System.out.print(node.val + " ");//特殊情况起始节点先输出处理
13         while (sk.size() > 0) {
14             Node t = sk.pop();
15             for (Node next : t.nexts) {
16                 if (!set.contains(next)) {
17                     sk.add(t);//一条路深入完回来后，还要用到这个节点去找第二条路，所以要让这个弹出节点回栈
18                     sk.add(next);//注意先入t,再入next,保证下一次栈中取出的是next.next,达到深度优先的要求
19                     set.add(next);
20                     System.out.print(t.val + " ");
21                     break;//因为是一条线深入，所以一次只能取一个next值，接下来就要结束这个循环，去找next的next
22                 }
23             }
24         }
25     }