深度优先搜索及java实现

偏执的太偏执、 2023-07-10 05:26 5阅读 0赞

深度优先搜索是图里面一种基础的搜索算法，英文简写DFS（depth First Search），深度优先搜索采用的方式是“”耿直boy型恋爱方式”--不撞南墙不回头，本文采用的图如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70][]

下面是DFS优先搜索的java实现，涉及到图Graph类、顶点Vertex类：

import java.util.ArrayList;
    import java.util.List;
    
    //图类
    public class Graph {
        //图中的顶点
        private List<Vertex> vertexes;
    
        public Graph(int len){
            //初始化时指定长度，避免扩容
            vertexes = new ArrayList<>(len);
        }
    
        public void addVertex(Vertex v){
            vertexes.add(v);
        }
    
        public List<Vertex> getVertexes() {
            return vertexes;
        }
    
        public void setVertexes(List<Vertex> vertexes) {
            this.vertexes = vertexes;
        }
    }

import com.algorithm.graph.bfs.VertexColor;
    import lombok.Getter;
    import lombok.Setter;
    
    import java.util.LinkedList;
    import java.util.List;
    
    //顶点类
    @Getter
    @Setter
    public class Vertex {
    	private VertexColor color;
    	//该顶点的连接队列
    	private List<Vertex> adjList;
    	//统计该节点在图顶点数组下标，对广度搜索非必要属性，仅用于统计使用
    	private int index ;
    	//发现时间
    	public int start;
    	//结束时间
    	public int end;
    	//上一节点
    	public Vertex pre;
    	
    	public Vertex(int index){
    		this.index = index;
    		adjList = new LinkedList<>();
    		this.color = VertexColor.WHITE;
    		this.start = 0;
    		this.end = 0;
    	}
    	
    	//添加邻接矩阵点
    	public void addVertex(Vertex v){
    		this.adjList.add(v);
    	}
    	
    	public VertexColor getColor() {
    		return color;
    	}
    	public void setColor(VertexColor color) {
    		this.color = color;
    	}
    	public List<Vertex> getAdjList() {
    		return adjList;
    	}
    	public void setAdjList(List<Vertex> adjList) {
    		this.adjList = adjList;
    	}
    	
    	@Override
    	public String toString(){
    		return String.format("节点:%d发现时间：%d，截止时间为:%d，上一节点为:%d", index,start,end,pre == null ? 0: pre.index);
    	}
    }

//顶点颜色枚举类
    public enum VertexColor {
    	WHITE,GRAY,BLACK;
    }

测试代码：

import com.algorithm.graph.bfs.VertexColor;
    import org.junit.Test;
    
    public class DFSTest {
    
        private int time = 0;
    
        @Test
        public void bfs(){
            Graph g= new Graph(7);
    
            Vertex v1 = new Vertex(1);
            Vertex v2 = new Vertex(2);
            Vertex v3 = new Vertex(3);
            Vertex v4 = new Vertex(4);
            Vertex v5 = new Vertex(5);
            Vertex v6 = new Vertex(6);
            Vertex v7 = new Vertex(7);
            //初始化图的顶点数组
            g.addVertex(v1);
            g.addVertex(v2);
            g.addVertex(v3);
            g.addVertex(v4);
            g.addVertex(v5);
            g.addVertex(v6);
            g.addVertex(v7);
            //初始化邻接矩阵
            v1.addVertex(v2);
            v1.addVertex(v4);
            //
            v2.addVertex(v4);
            v2.addVertex(v7);
            //
            v3.addVertex(v1);
            v3.addVertex(v5);
            //
            v4.addVertex(v5);
            v4.addVertex(v6);
            //
            v5.addVertex(v6);
            //
            v7.addVertex(v6);
            //
            init(g);
            for(Vertex v:g.getVertexes()){
                if(v.getColor() == VertexColor.WHITE){
                    dfsVisit(g,v);
                }
            }
            for(Vertex v:g.getVertexes()){
                System.out.println(v.toString());
            }
        }
    
        private void init(Graph g){
            for(Vertex v:g.getVertexes()){
                v.setColor(VertexColor.WHITE);
                v.pre = null;
                v.start =-1;
                v.end =0;
            }
            //重置time
            time = 0;
        }
    
        private void dfsVisit(Graph g,Vertex v){
            time = time +1;
            v.start = time;
            v.setColor(VertexColor.GRAY);
            for(Vertex c:v.getAdjList()){
                if(c.getColor() == VertexColor.WHITE){
                    c.pre = v;
                    dfsVisit(g,c);
                }
            }
            //遍历完子节点
            v.setColor(VertexColor.BLACK);
            time = time +1;
            v.end = time;
        }
    }

输出结果如下：

节点:1发现时间：1，截止时间为:12，上一节点为:0  
节点:2发现时间：2，截止时间为:11，上一节点为:1  
节点:3发现时间：13，截止时间为:14，上一节点为:0  
节点:4发现时间：3，截止时间为:8，上一节点为:2  
节点:5发现时间：4，截止时间为:7，上一节点为:4  
节点:6发现时间：5，截止时间为:6，上一节点为:5  
节点:7发现时间：9，截止时间为:10，上一节点为:2

PS：

1、深度优先算法的时间复杂度为O(V+E)，V为顶点数目，E为图中边的条数

2、深度优先搜索的前驱子图构成一个由多棵深度优先树构成的深度优先森林，且所有的深度优先树之间互不相交

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200229205608825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3,size_16,color_FFFFFF,t_70