广度优先遍历(BFS)和深度优先遍历(DFS)

是什么?

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。[1](p603)这种算法不会根据图的结构等信息调整执行策略

广度优先搜索算法(英语:Breadth-First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。

来自维基百科

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* @author CongZ
* @classname DFSandBFS
* DFS Depth First Search 深度优先算法
* BFS Breadth FirstSearch 广度优先算法
* @create 2020/3/31
**/

public class DFSandBFS {
public static void main(String[] args) {
TreeNode head = new TreeNode(1);
TreeNode two = new TreeNode(2);
TreeNode three = new TreeNode(3);
TreeNode four = new TreeNode(4);
TreeNode five = new TreeNode(5);
TreeNode six = new TreeNode(6);
TreeNode seven = new TreeNode(7);
TreeNode eight = new TreeNode(8);
head.left = two;
head.right = three;
two.left = four;
two.right = five;
three.left = six;
three.right = seven;
four.right=eight;
System.out.print("广度优先遍历结果:");
System.out.println();
new DFSandBFS().BFS(head);
System.out.println();
System.out.print("深度优先遍历结果:");
System.out.println();
new DFSandBFS().DFS(head);
}

/**
* 广度优先
* @param headNode
*/
public void BFS(TreeNode headNode) {
if (headNode == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(headNode);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.node+",");
if (null != node.left) {
queue.add(node.left);
}
if (null != node.right) {
queue.add(node.right);
}
}
}

/**
* 深度优先
* @param headNode
*/
public void DFS(TreeNode headNode){
if(headNode !=null){
Stack<TreeNode>stack=new Stack<>();
stack.add(headNode);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
System.out.print(node.node+",");
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
}
}

static class TreeNode {
int node;
TreeNode left;
TreeNode right;

public TreeNode(int data) {
node = data;
}
}
}

结果:

1
2
3
4
广度优先遍历结果:
1,2,3,4,5,6,7,8,
深度优先遍历结果:
1,2,4,8,5,3,6,7,

广度优先遍历利用的是队列的先进先出特性

步骤:

1、获取到根节点1 ,判断根节点是否有子节点,如果有,添加到队列

2、移除根节点1,剩下节点2和节点3

3、移除节点2,判断节点2是否有子节点,添加到队列节点4和节点5 ,剩下节点3和节点4和节点5

4、依次移除节点3,判断节点3是否有子节点,添加到队列节点6和节点7,剩下节点4,5,6,7

5、依次循环,直到判断所有子节点为空

深度优先遍历利用的是栈的先进后出特性

步骤:

1、获取根节点1,判断根节点是否有子节点,如果有,添加到栈

2、移除根节点1,剩下节点2和节点3

3、移除节点2,判断节点2,是否有子节点,添加到队列,节点4,5,剩下节点3,4,5

4、这里有点区别就是,移除的是节点4,因为节点4是最后进栈的,所以最先出去,剩下节点3,5

5、移除节点5,判断是否有子节点,剩下节点3

6、依次循环,直到判断所有子节点为空

深度遍历(DFS)又分为三种

前序遍历,后序遍历,中序遍历,上面的代码指的是中序遍历

-------------本文结束感谢您的阅读-------------
0%