Breadth First Search(BFS) and Depth First Search(DFS) - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki
图Graph, 深度优先遍历(DFS), 广度优先遍历(BFS)【数据结构和算法入门9】
图的存储及广度、深度优先搜索
洛谷 普及组试炼场 - 深度优先搜索（DFS）
洛谷 普及组试炼场 - 广度优先搜索（BFS）
| 广度优先搜索BFS | 深度优先搜索DFS |
|---|---|
 |
 |
图的广度优先搜索（BFS）和深度优先搜索（DFS）算法解析
数据结构：图之DFS与BFS的复杂度分析
无权重最短路径问题：广度优先搜索 & Java 实现
public class BFSTraverse<T> {
// 访问路径
private ArrayList<Node<T>> path;
// 标记结点是否已经被访问
private boolean[] visited;
private AdjacencyList<T> adjList;
// 构造辅助队列
Queue<ArrayList<AdjListNode>> qn;
public BFSTraverse(AdjacencyList<T> adjList) {
this.adjList = adjList;
this.visited = new boolean[adjList.size()];
Arrays.fill(visited, false);
}
/**
* 通过辅助队列，实现Bfs算法
* 1. 先将一个链表的头节点加入队列
* 2. 通过for，链表内每一个节点所对应的链表的头结点加入队列中
* 3. 改变节点的状态， 将节点加入到路径中即可
*/
public void BFS() {
if (adjList == null || adjList.getNodes().size() == 0) {
return;
}
path = new ArrayList<>();
qn = new LinkedList<>();
// 确保所有结点被访问过，得出的结果正确性毋庸置疑
for (int i = 0; i < adjList.size(); i++) {
// 判断结点是否被访问过
if (!visited[i]) {
// 将该结点标记访问过
visited[i] = true;
// 添加到路径中
path.add(adjList.getNodes().get(i));
// 添加改链表的头结点
qn.add(adjList.getNodes().get(i).getRoot());
// 对该结点的链表进行访问
BFSVisit();
}
}
}
private void BFSVisit() {
while (!qn.isEmpty()) {
// 从第一个开始出队
ArrayList<AdjListNode> list = qn.remove();
// 这个 for 用于将所有该链表里的 结点 加入到队列中
for (AdjListNode adjListNode : list) {
// 判断结点是否被访问过
if (!visited[adjListNode.getIndex()]) {
// 将该结点标记访问过
visited[adjListNode.getIndex()] = true;
// 添加到路径中
path.add(adjList.getNodes().get(adjListNode.getIndex()));
// 将该节点所代表的链表加入到队列中
qn.add(adjList.getNodes().get(adjListNode.getIndex()).getRoot());
}
}
}
}
public void print() {
System.out.print("搜索路径： " + path.get(0).getData());
for (int i = 1; i < path.size(); i++) {
System.out.print(" -> " + path.get(i).getData());
}
System.out.println();
}
}
public class DFSTraverse<T> {
// 访问路径
private ArrayList<Node<T>> path;
// 标记结点是否已经被访问
private boolean[] visited;
private AdjacencyList<T> adjList;
public DFSTraverse(AdjacencyList<T> adjList) {
this.adjList = adjList;
this.visited = new boolean[adjList.size()];
Arrays.fill(visited, false);
}
/**
* 第一个for用于遍历所有的结点 只有全部结点都被访问过才有可能返回
* 遍历步骤:
* 1. 如果该节点未被访问过，则接下来访问它的链表
* 2. 将链表中每一个元素当做新的链表头进行递归操作
* 3. path用于记录访问顺序
*
* 总结 ：
* 第一个for确保所有节点都被访问过
* visited则确保每条链表都被检查过，但不一定进行操作
*/
public void DFS() {
if (adjList == null || adjList.getNodes().size() == 0) {
return;
}
path = new ArrayList<>();
// 确保所有结点被访问过，得出的结果正确性毋庸置疑
for (int i = 0; i < adjList.size(); i++) {
// 判断结点是否被访问过
if (!visited[i]) {
// 将该结点标记访问过
visited[i] = true;
// 添加到路径中
path.add(adjList.getNodes().get(i));
// 对该结点的链表进行访问
DFSVisit(adjList.getNodes().get(i).getRoot());
}
}
}
private void DFSVisit(ArrayList<AdjListNode> list) {
// list.get(i).getIndex()代表某个结点的下标
for (int i = 0; i < list.size(); i++) {
// 判断结点是否被访问过
if (!visited[list.get(i).getIndex()]) {
// 将该结点标记访问过
visited[list.get(i).getIndex()] = true;
// 添加到路径中
path.add(adjList.getNodes().get(list.get(i).getIndex()));
// 对该节点的链表进行访问
DFSVisit(adjList.getNodes().get(list.get(i).getIndex()).getRoot());
}
}
}
public void print() {
System.out.print("搜索路径： " + path.get(0).getData());
for (int i = 1; i < path.size(); i++) {
System.out.print(" -> " + path.get(i).getData());
}
System.out.println();
}
}
ArrayList<Node<String>> nodes = new ArrayList<>();
nodes.add(new Node<String>("V1"));
nodes.add(new Node<String>("V2"));
nodes.add(new Node<String>("V3"));
nodes.add(new Node<String>("V4"));
nodes.add(new Node<String>("V5"));
nodes.add(new Node<String>("V6"));
nodes.add(new Node<String>("V7"));
nodes.add(new Node<String>("V8"));
AdjacencyList<String> adjList = new AdjacencyList<String>(nodes);
adjList.addEdge(0, 1, 0);
adjList.addEdge(0, 2, 0);
adjList.addEdge(1, 3, 0);
adjList.addEdge(2, 5, 0);
adjList.addEdge(2, 6, 0);
adjList.addEdge(3, 7, 0);
adjList.addEdge(4, 1, 0);
adjList.addEdge(4, 7, 0);
adjList.addEdge(5, 6, 0);
DFSTraverse<String> dfs = new DFSTraverse<String>(adjList);
dfs.DFS();
dfs.print();
// 搜索路径： V1 -> V2 -> V4 -> V8 -> V3 -> V6 -> V7 -> V5
BFSTraverse<String> bfs = new BFSTraverse<String>(adjList);
bfs.BFS();
bfs.print();
// 搜索路径： V1 -> V2 -> V3 -> V4 -> V6 -> V7 -> V8 -> V5
| 广度优先搜索BFS | 深度优先搜索DFS | |
|---|---|---|
| 通俗解释 | 类似层次遍历，一行一行搜索 | 一头扎到底 |
| 父边 | 红边为各个结点的父边 | 红边为各个结点的父边 |
 |
 |
|
| 父边构成一棵树，无环 | 父边构成一棵树，无环 | |
| 父边是结点s到其它各个结点的最短路径 | 父边不是结点s到其它各个结点的最短路径 | |
| 时间复杂度（邻接表） | O(V + E) | O(V + E) |
| 时间复杂度（邻接矩阵） | O(V^2) | O(V^2) |
| 数据结构 |
队列Queue 每次访问一个结点，把所有该结点的未访问的邻结点都添加到队列 |
栈Stack 每次访问一个结点，把所有该结点的未访问的邻结点都添加到栈 |
| 访问了每一个结点 访问了每一条边 没有访问每一条路径 这是BFS不能用来找到**加权图的最短路径**的原因 |
访问了每一个结点 访问了每一条边 没有访问每一条路径 这是DFS不能用来找到**加权图的最短路径**的原因 |
- 父边Parent Edge：通过BFS/DFS，通过某条边e第一次访问到当前的结点v，则e为v的父边
- 使用BFS或DFS遍历每一条路径是非常昂贵的
-
- 如上图，每个菱形都有2种选择（选上两条边或下两条边），从src到dist有2^(n/4)种不同的路径，n为边数
-
- 广度优先搜索BFS可用于求无权图的最短路径
- 啥时候O(E +V) 可以看成是O(E +V) = O(E)，Connected graph 的时候，因为不connected的话V可能远大于E，connected的话E至少是V-1
迷宫可以以二维数组来存储表示。0表示通路，1表示障碍
