图论（六）图的深度优先遍历DFS(非递归方式)
2022-04-09 本文已影响0人
小波同学
一、深度优先搜索
深度优先搜索是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。
对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
DFS的非递归实现方式相比于BFS应该说大同小异，只是把queue换成了stack而已，stack具有后进先出LIFO(Last Input First Output)的特性，DFS的操作步骤如下：
- 1、把起始点放入stack；
- 2、重复下述3步骤，直到stack为空为止：
- 从stack中访问栈顶的点；
- 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入stack中；
- 如果此点没有尚未遍历的邻接点，则将此点从stack中弹出。
二、深度优先遍历(非递归)图文演示
下面结合一个图(graph)的实例，说明DFS的工作过程和原理：
- 1、将起始节点1放入栈stack中，标记为已遍历。
- 2、从stack中访问栈顶的节点1，找出与节点1邻接的节点，有2、9两个节点，我们可以选择其中任何一个，选择规则可以人为设定，这里假设按照节点数字顺序由小到大选择，选中的是2，标记为已遍历，然后放入stack中。
- 3、从stack中取出栈顶的节点2，找出与节点2邻接的节点，有1、3、5三个节点，节点1已遍历过，排除；3、5中按照预定的规则选中的是3，标记为已遍历，然后放入stack中。
- 4、从stack中取出栈顶的节点3，找出与节点3邻接的节点，有2、4两个节点，节点2已遍历过，排除；选中的是节点4，标记为已遍历，然后放入stack中。
- 5、从stack中取出栈顶的节点4，找出与节点4邻接的节点，有3、5、6三个节点，节点3已遍历过，排除；选中的是节点5，标记为已遍历，然后放入stack中。
- 6、从stack中取出栈顶的节点5，找出与节点5邻接的节点，有2、4两个节点，节点2、4都已遍历过，因此节点5没有尚未遍历的邻接点，则将此点从stack中弹出。
- 7、当前stack栈顶的节点是4，找出与节点4邻接的节点，有3、5、6三个节点，节点3、5都已遍历过，排除；选中的是节点6，标记为已遍历，然后放入stack中。
- 8、当前stack栈顶的节点是6，找出与节点6邻接的节点，有4、7、8三个节点，4已遍历，按照规则选中的是7，标记为已遍历，然后放入stack中。
- 9、当前stack栈顶的节点是7，找出与节点7邻接的节点，只有节点6，已遍历过，因此没有尚未遍历的邻接点，将节点7从stack中弹出。
- 10、当前stack栈顶的节点是6，找出与节点6邻接的节点，有节点7、8，7已遍历过，因此将节点8放入stack中。
- 11、当前stack栈顶的节点是8，找出与节点8邻接的节点，有节点1、6、9，1、6已遍历过，因此将节点9放入stack中。
-
12、当前stack栈顶的节点是9，没有尚未遍历的邻接点，将节点9弹出，依次类推，栈中剩余节点8、6、4、3、2、1都没有尚未遍历的邻接点，都将弹出，最后栈为空。
-
13、DFS遍历完成。
三、邻接表进行深度优先遍历
3.1 构建数据结构
public class Graph {
//顶点个数
private int V;
//边的条数
private int E;
//领接表的底层存储结构
private TreeSet<Integer>[] adj;
}
3.2 通过该结构定义，构造一个图(无向图）
/**
* @Author: huangyibo
* @Date: 2022/3/28 1:02
* @Description: 领接表, 目前只支持无向无权图
*/
public class Graph {
//顶点个数
private int V;
//边的条数
private int E;
//领接表的底层存储结构
private TreeSet<Integer>[] adj;
public Graph(String filename){
File file = new File(filename);
try {
Scanner scanner = new Scanner(file);
V = scanner.nextInt();
if(V < 0){
throw new IllegalArgumentException("V must be non-negative");
}
adj = new TreeSet[V];
//初始化领接表
for (int i = 0; i < V; i++) {
adj[i] = new TreeSet<>();
}
E = scanner.nextInt();
if(E < 0){
throw new IllegalArgumentException("E must be non-negative");
}
for (int i = 0; i < E; i++) {
int a = scanner.nextInt();
//校验顶点a是否合法
validateVertex(a);
int b = scanner.nextInt();
//校验顶点b是否合法
validateVertex(b);
//校验是否是自环边
if(a == b){
throw new IllegalArgumentException("Self Loop is Detected!");
}
//校验是否是平行边
if(adj[a].contains(b)){
throw new IllegalArgumentException("Parallel Edges are Detected!");
}
adj[a].add(b);
adj[b].add(a);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
/**
* 校验顶点是否合法
* @param v
*/
private void validateVertex(int v){
if(v < 0 || v >= V){
throw new IllegalArgumentException("vertex " + v + " is invalid");
}
}
/**
* 获取顶点个数
* @return
*/
public int V(){
return V;
}
/**
* 获取边的条数
* @return
*/
public int E(){
return E;
}
/**
* 图中是否存在v到w的边
* @param v
* @param w
* @return
*/
public boolean hasEdge(int v, int w){
//校验顶点v是否合法
validateVertex(v);
//校验顶点w是否合法
validateVertex(w);
return adj[v].contains(w);
}
/**
* 返回和v相邻的顶点
* @param v
* @return
*/
public Iterable<Integer> adj(int v){
//校验顶点v是否合法
validateVertex(v);
return adj[v];
}
/**
* 返回顶点v的度
* 顶点v的度（Degree）是指在图中与v相关联的边的条数
* @param v
* @return
*/
public int degree(int v){
//校验顶点v是否合法
validateVertex(v);
return adj[v].size();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\n", V, E));
for (int v = 0; v < V; v++) {
sb.append(String.format("%d : ", v));
for (Integer w : adj[v]) {
sb.append(String.format("%d ", w));
}
sb.append("\n");
}
return sb.toString();
}
}
3.3 邻接表的深度优先算法(非递归)
/**
* @Author: huangyibo
* @Date: 2022/3/28 1:02
* @Description: 图的深度优先遍历, 非递归方式
*/
public class GraphDFS {
private Graph G;
/**
* 图的顶点是否已经被遍历过
*/
private boolean[] visited;
//图的深度优先遍历结果
private List<Integer> order = new ArrayList<>();
public GraphDFS(Graph G){
this.G = G;
visited = new boolean[G.V()];
//循环所有顶点, 防止一个图出现多个连通图(连通分量)的情况
for (int v = 0; v < G.V(); v++) {
if(!visited[v]){
dfs(v);
}
}
}
/**
* 图的深度优先遍历, 非递归方式
* @param source
*/
private void dfs(int source) {
Stack<Integer> stack = new Stack<>();
//将源结点压入栈顶
stack.push(source);
//标记为已访问
visited[source] = true;
//如果栈不为空
while(!stack.isEmpty()){
Integer v = stack.pop();
//当前出栈顶点添加到图的深度优先遍历结果集
order.add(v);
//遍历顶点V的相邻顶点
for (Integer w : G.adj((v))) {
//如果没有遍历过
if(!visited[w]){
//顶点w压入栈顶
stack.push(w);
//标记w为已访问
visited[w] = true;
}
}
}
}
/**
* 图的深度优先遍历结果集
* @return
*/
public List<Integer> order(){
return order;
}
public static void main(String[] args) {
Graph graph = new Graph("src/main/resources/g1.txt");
GraphDFS graphDFS = new GraphDFS(graph);
System.out.println(graphDFS.order());
}
}
g1.txt
7 6
0 1
0 2
1 3
1 4
2 3
2 6
参考：
https://blog.csdn.net/saltriver/article/details/54429068
