【面试干货】DFS、BFS 算法

【面试干货】DFS、BFS 算法

• 1、实现思想
• 2、代码实现

1、实现思想

通过递归或队列方式依次访问图中的节点，并使用辅助数组记录已访问节点，以实现遍历整个图的目的。实现深度优先搜索和广度优先搜索两种遍历算法。

DFS通过递归地深入图中的每个分支，直到无法再继续深入为止，然后回溯到上一个分支；

而BFS则通过逐层访问图中的节点，从起始节点开始向外扩展，直到访问到所有可达节点。

在实现中，DFS使用递归方式遍历节点，而BFS则利用队列实现节点的逐层访问。通过辅助数组记录已经访问的节点，避免重复访问，并最终完成整个图的遍历。

2、代码实现

package csdn; 
public class GraphTraversal { // 定义类GraphTraversal
static int[][] graph = new int[][]{{0, 1, 1, 0, 0, 0}, // 定义邻接矩阵表示的图，每行代表一个顶点的相邻顶点情况
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}};
static int[] help = new int[graph.length]; // 用来记录已经遍历过的元素
// DFS(深度优先遍历)
public static void dfsTraversing(int node, int[][] graph) { // 定义DFS遍历方法，参数为起始节点和图的邻接矩阵
help[node] = 1; // 标记当前节点已经遍历过
System.out.println(node); // 打印当前节点
for (int i = 0; i < graph[node].length; ++i) { // 遍历当前节点的所有相邻节点
if (help[i] == 0 && i != node && graph[node][i] == 1) { // 如果相邻节点未被遍历且与当前节点相连
dfsTraversing(i, graph); // 递归调用DFS遍历相邻节点
}
}
}
// BFS(广度优先遍历)
public static void bfsTraversing(int[][] graph) { // 定义BFS遍历方法，参数为图的邻接矩阵
int[] queue = new int[graph.length]; // 创建队列用于存储待访问的节点
int cnt = 1; // 记录队列中元素个数
queue[0] = 0; // 将第一个顶点加入队列作为起始顶点
help[0] = 1; // 标记起始顶点已经被访问
System.out.println(0); // 打印起始顶点
for (int i = 0; i < cnt; ++i) { // 遍历队列中的节点
for (int j = 0; j < graph[queue[i]].length; ++j) { // 遍历当前节点的相邻节点
if (queue[i] != j && graph[queue[i]][j] == 1 && help[j] == 0) { // 如果相邻节点未被遍历且与当前节点相连
help[j] = 1; // 标记相邻节点已经被访问
queue[cnt++] = j; // 将相邻节点加入队列
System.out.println(j); // 打印相邻节点
}
}
}
}
public static void main(String[] args) { // 主方法
System.out.println("深度优先遍历："); // 打印DFS遍历提示
dfsTraversing(0, graph); // 调用DFS遍历方法
resetHelpArray(); // 重置help数组
System.out.println("广度优先遍历："); // 打印BFS遍历提示
bfsTraversing(graph); // 调用BFS遍历方法
}
// 重置help数组，以便重新运行遍历算法
private static void resetHelpArray() { // 定义重置help数组的方法
for (int i = 0; i < help.length; i++) { // 遍历help数组
help[i] = 0; // 将元素值重置为0
}
}
}

DFS遍历:

1. 从顶点0开始，DFS首先沿着边到达顶点1。
2. 接着，它从顶点1沿着边到达顶点3。
3. 然后，它从顶点3沿着边到达顶点5。
4. 由于顶点5是一个叶节点，DFS回溯到顶点3，并尝试访问顶点3的其他相邻节点，但没有找到。
5. 接着，DFS回溯到顶点1，并尝试访问顶点1的其他相邻节点，发现了顶点2。
6. 最后，DFS访问了顶点2，但没有其他相邻节点可供访问，遍历结束。

BFS遍历:

8. 从顶点0开始，BFS首先访问了顶点0，并将顶点0的相邻节点1加入了队列。
9. 接着，BFS访问了队列中的下一个顶点，即顶点1，并将顶点1的相邻节点2、3加入了队列。
10. 然后，BFS访问了队列中的下一个顶点，即顶点2，并发现没有其他相邻节点。
11. 接着，BFS访问了队列中的下一个顶点，即顶点3，并将顶点3的相邻节点5加入了队列。
12. 继续这个过程，直到队列为空，遍历结束。