一、深度优先搜索 DFS
概述
深度优先搜索（Depth First Search，DFS）是一种用于遍历图或树数据结构的递归算法。该算法从根节点开始，尽可能深地探索每个分支，直到无法继续前进为止，然后回溯到上一个节点，继续探索其他分支。为了避免重复访问节点，需要使用额外的内存（通常是一个栈）来跟踪已经发现的节点。
深度优先搜索的时间复杂度为O(V + E)，其中V是节点数，E是边数。空间复杂度为O(V)。
深度优先搜索在许多领域有广泛的应用，例如寻找路径、检测图是否为二分图、寻找强连通分量和检测图中的环等。
dfs.gif
实现思路
深度优先搜索的实现可以使用递归或非递归方式。递归实现是最直观的方式，但可能在处理大型图时导致栈溢出。非递归实现使用一个栈来模拟递归过程，可以处理更大规模的图。
非递归实现步骤
- 将任意一个节点作为起始节点，并将其标记为已访问。
- 将起始节点的所有未访问邻居节点加入栈中。
- 从栈中取出栈顶节点，并将其标记为已访问。
- 将该节点的所有未访问邻居节点加入栈中。
- 重复步骤3和步骤4，直到栈为空。
下面是深度优先搜索的伪代码实现：
procedure DFS(G, v) is
label v as discovered
for each edge (v, w) in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
二、广度优先搜索 BFS
概述
广度优先搜索（Breadth First Search，BFS）是一种用于遍历图或树数据结构的算法。该算法从根节点开始，逐层地遍历节点，先访问当前层的所有节点，然后再访问下一层的节点。在搜索过程中，使用一个队列来存储待访问的节点，并使用一个标记数组来记录已经访问过的节点，以避免重复访问。
广度优先搜索的时间复杂度为O(V + E)，其中V是节点数，E是边数。空间复杂度为O(V)。
广度优先搜索在许多领域有广泛的应用，例如寻找最短路径、检测图是否连通、生成迷宫的最短路径等。
bfs.gif
实现思路
广度优先搜索的实现可以使用队列来模拟搜索过程。通过不断将邻居节点加入队列，并按照先进先出的顺序访问节点，可以确保按层级遍历图或树。
实现步骤
- 将起始节点放入队列中，并标记为已访问。
- 从队列中取出一个节点，并访问该节点。
- 将该节点的所有未访问邻居节点加入队列，并标记为已访问。
- 重复步骤2和步骤3，直到队列为空。
下面是广度优先搜索的伪代码实现：
procedure BFS(G, start) is
let Q be a queue
Q.enqueue(start)
mark start as visited
while Q is not empty do
v := Q.dequeue()
process v
for each neighbor w of v do
if w is not visited then
Q.enqueue(w)
mark w as visited
三、Java代码示例
实现思路:
用数组表示顶点, 数组元素为LinkedList<Integer>表示边. 例如,
adjList[0]有列表[1, 3, 5] --代表顶点0有三条边, 分别连接顶点1, 3, 5
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class DfsAndBfs {
// adjLists表示顶点集合,每个顶点都有List.size()条边
private final LinkedList<Integer>[] adjLists;
// 表示第i个顶点是否访问过
private final boolean[] visited;
/**
* 指定有几个节点
* @param vertices 节点数
*/
DfsAndBfs(int vertices) {
adjLists = new LinkedList[vertices];
visited = new boolean[vertices];
for (int i = 0; i < vertices; i++)
adjLists[i] = new LinkedList<>();
}
/**
* 输入起点和终点, 构造定点的边
* @param src 起点
* @param dest 终点
*/
void addEdge(int src, int dest) {
adjLists[src].add(dest);
}
/**
* 深度优先搜索, 递归实现
* @param start 起始节点
*/
void DFS(int start) {
visited[start] = true;
System.out.print(start);
for (int adj : adjLists[start]) {
if (!visited[adj]) {
System.out.print(" -> ");
DFS(adj);
}
}
}
/**
* 深度优先搜索, 非递归实现
* @param start 起始节点
*/
void DFS_notRecursion(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
visited[start] = true;
while (!stack.isEmpty()) {
int vertex = stack.pop();
System.out.print(vertex);
// 将其子元素从右往左循环入栈
for (int i = adjLists[vertex].size() - 1; i >= 0; i--) {
Integer eachTarget = adjLists[vertex].get(i);
if (!visited[eachTarget]) {
visited[eachTarget] = true;
stack.push(eachTarget);
}
}
if (!stack.isEmpty()) {
System.out.print(" -> ");
}
}
}
/**
* 广度优先搜索
* @param start 起始节点
*/
void BFS(int start) {
visited[start] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
// 取出头部元素,将其子元素加入到队列尾部
int vertex = queue.poll();
System.out.print(vertex);
for (int adj : adjLists[vertex]) {
if (!visited[adj]) {
visited[adj] = true;
queue.add(adj);
}
}
if (!queue.isEmpty()) {
System.out.print(" -> ");
}
}
}
public static void main(String[] args) {
testDfs();
testDFS_notRecursion();
testBfs();
}
private static void testDfs() {
DfsAndBfs g = new DfsAndBfs(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
System.out.print("Depth First Traversal: ");
g.DFS(0);
System.out.println();
}
private static void testDFS_notRecursion() {
DfsAndBfs g = new DfsAndBfs(6);
g.addEdge(0, 1);
g.addEdge(0, 3);
g.addEdge(0, 5);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(1, 5);
System.out.print("Depth First Traversal Not Recursion: ");
g.DFS_notRecursion(0);
System.out.println();
}
private static void testBfs() {
DfsAndBfs g = new DfsAndBfs(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(2, 5);
System.out.print("Breadth First Traversal: ");
g.BFS(0);
System.out.println();
}
}
网友评论