图论Dfs干货速递
2024-11-11 17:37:48
发布于：广东
我们要访问图中的每个节点，即图的遍历。
图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。
我们根据访问节点的顺序与方式（根据搜索方法），可以分为广度优先（BFS）和深度优先（DFS），这是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路(走迷宫)，搜索引擎，爬虫等。
我们分别来介绍
一、深度优先（DFS）
深度优先搜索（Depth-First-Search），简称 DFS。
现在需要访问每个节点，且只访问一次，可以看到，图分成了很多之路，
主要思路是从图中一个未访问的顶点 V （比如A）开始，沿着一条路一直走到底，深入到不能再深入为止（够深），然后从这条路尽头的节点回退到上一个节点， 如果上一个节点存在没有探索的分支，便继续探索若没有则继续回退，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
这就是暴力穷举，
1.1 图解过程
1、我们从根节点 A 开始遍历，它相邻的节点有 B，E，先遍历节点 B，再遍历 B 的子节点 C
2、上图中一条路已经走到底了(C是叶子节点，再无可遍历的节点)，此时就从 C 回退到上一个节点 B，看下节点 B 是否还有除 C 以外的节点，发现 B有 D节点，然后遍历D，
3、同理，上图中一条路已经走到底了(D是叶子节点，再无可遍历的节点)，此时就从 D 回退到上一个节点 B，B的节点都遍历过了，然后在回到A， 同样的逻辑，再到，E、F
1.2 java 实现
package com.test;
import java.util.ArrayList;
import java.util.List;
public class DepthFirstSearch {
// 定义图结构
private List<Integer>[] graph;
// 构造函数，初始化图结构
public DepthFirstSearch(int numVertices) {
graph = new ArrayList[numVertices];
for (int i = 0; i < numVertices; i++) {
graph[i] = new ArrayList<>();
}
}
// 添加边
public void addEdge(int v1, int v2) {
graph[v1].add(v2);
}
// 深度优先搜索算法实现
public void dfs(int start) {
boolean[] visited = new boolean[graph.length]; // 标记每个顶点是否被访问过
dfsHelper(start, visited); // 递归实现深度优先搜索算法
}
// 递归实现深度优先搜索算法
private void dfsHelper(int vertex, boolean[] visited) {
visited[vertex] = true; // 标记当前顶点已被访问过
System.out.print(geta(vertex)); // 输出当前顶点编号
for (int neighbor : graph[vertex]) { // 遍历当前顶点的邻居顶点
if (!visited[neighbor]) { // 如果邻居顶点未被访问过，则递归访问它
dfsHelper(neighbor, visited);
}
}
}
private String geta(int index){
switch (index) {
case 0:
return "A";
case 1:
return "B";
case 2:
return "C";
case 3:
return "D";
case 4:
return "E";
case 5:
return "F";
}
return "";
}
希望ac君能加“精”或“置顶”
这里空空如也
有帮助，赞一个