1.广度优先搜索与队列
1.1使用广度优先搜索的两种情景:
1.遍历图或树
2.寻找最短路径
1.2模板
1.2.1寻找最短路径
为什么是最短?
从根节点出发,按层遍历,当目标第一个被访问一定是层数最少的访问
模板一
对于一个节点肯能访问多次
适用于1.没有循环的情况(树的遍历)2.确实希望多次将节点添加到队列中
/** * Return the length of the shortest path between root and target node. */
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
模板二
有时,确保我们永远不会访问一个结点两次很重要。否则,我们可能陷入无限循环。如果是这样,我们可以在上面的代码中添加一个哈希集来解决这个问题。
如果节点有序号且知道总个数也可以使用数组来代替哈希集
/** * Return the length of the shortest path between root and target node. */
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to used;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
1.2.2遍历
只需要去掉上述两个模板的return语句即可,即只有当队列为空时才结束。
对于图来说
即多源点问题,只需要把所有的源都加入队列再进行搜索即可。
2深度优先搜索与堆栈
在大多数情况下,我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别:遍历顺序。
与 BFS 不同,更早访问的结点可能不是更靠近根结点的结点。因此,你在 DFS 中找到的第一条路径可能不是最短路径。
2.1模板
2.1.1模板 - 递归
当我们递归地实现 DFS 时,似乎不需要使用任何栈。但实际上,我们使用的是由系统提供的隐式栈,也称为调用栈(Call Stack)。
/* * Return true if there is a path from cur to target. */
boolean DFS(Node cur, Node target, Set<Node> visited) {
return true if cur is target;
for (next : each neighbor of cur) {
if (next is not in visited) {
add next to visted;
return true if DFS(next, target, visited) == true;
}
}
return false;
}
2.1.2模板 - 非递归
递归解决方案的优点是它更容易实现。 但是,存在一个很大的缺点:如果递归的深度太高,你将遭受堆栈溢出。 在这种情况下,您可能会希望使用 BFS,或使用显式栈实现 DFS。
/* * Return true if there is a path from cur to target. */
boolean DFS(int root, int target) {
Set<Node> visited;
Stack<Node> s;
add root to s;
while (s is not empty) {
Node cur = the top element in s;
return true if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to s;
add next to visited;
}
}
remove cur from s;
}
return false;
}