软1802黄汨文

用户名：Moyna

访问量：1420

签　名：

等　　级
排　　名	14411
经　　验	880
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	湖南理工学院
专　　业

　　自我简介：

TA的其他文章

数据结构-图的遍历——BFS广度优先搜索-题解（Java代码）
浏览：358

蓝桥杯算法提高VIP-和最大子序列-题解（Java代码）
浏览：324

你可能喜欢

数据结构-图的遍历——DFS深度优先搜索-题解（好像木有JAVA代码的，那我就补充一下

　　作者: 软1802黄汨文　　　　发表时间：2020-05-18 18:33:38 浏览：203　|　评论：0　

原题链接：数据结构-图的遍历-DFS深度优先搜索(深搜)

### DFS过程：
已本题的输入样本为例：
1. 首先找一个未被遍历的顶点（默认是0）,如，0被访问过，则isVisited[0] = true;
2. 通过赋过值得邻接矩阵，找出0的下一个邻接点，有邻接矩阵知为1；
3. 到了顶点1，根据之前做的标记显示，所有邻接点都被访问过了，此时从1回退到0，通过查看 0 ，找到一个未被访问过的顶点 3，继续遍历，直到所有连通顶点被访问。
4. 考虑到存在孤立的顶点，需要将标记数组在遍历一次，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。

**这实际是一个不断回溯的过程。**

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main{
        static ArrayList<Integer> vertexList;//保存顶点
        static int[][] edges;//存储图的对应邻接矩阵
        static int numberOfEdges;//边的数目
        boolean[] isVisited;//判断这个顶点是否被访问
        static  String s = "";
        //构造函数
        public Main(int n){//n表示节点的个数
            //初始化下列变量;
            vertexList = new ArrayList<>(n);
            edges = new int[n][n];
            numberOfEdges = 0;
            isVisited = new boolean[n];
        }
        //输入顶点
        public void insertVertex(int n){
            for(int i = 0;i<n;i++){
                vertexList.add(i);
            }
        }
    
    
        //获取第一个邻接点
        public int getFirstNeighbor(int index){
            for(int j = 0;j<vertexList.size();j++){
                //如果存在，返回对应的下标
                if(edges[index][j]>0){
                    return j;
                }
            }
            return -1;
        }
    
        //获取下一个邻接点
        public int getNextNeighbor(int v1,int v2){
            for(int j = v2+1;j<vertexList.size();j++){
                if(edges[v1][j]>0){
                    return j;
                }
            }
            return -1;
        }
    
        //深度优先搜索
        public void dfs(boolean[] isVisited,int index){
            s+=vertexList.get(index)+" ";//要输出的字符串
    
            isVisited[index]= true;
    
            int w = getFirstNeighbor(index);//获取该顶点的第一个邻接点
    
            while(w!=-1){
                if (!isVisited[w]){
                    dfs(isVisited,w);
                }
    
                w = getNextNeighbor(index,w);
            }
    
        }
    //方法重载,考虑到存在节点为孤立顶点
        public void dfs(){
            for(int i = 0;i<vertexList.size();i++){
                if (!isVisited[i]){
                    dfs(isVisited,i);
                }
            }
        }
    
    
    
        public static void main(String[] args) {
             Scanner scanner = new Scanner(System.in);
             int n = scanner.nextInt();//顶点个数
    
             Main graph = new Main(n);
    
             graph.insertVertex(n);
			 
             for(int i = 0;i<n;i++){
                for(int j = 0;j<n;j++){
				//输入矩阵的值(0或1)
                    edges[i][j] = scanner.nextInt();
                }
            }
    
             graph.dfs();
            System.out.println(s.trim());
        }
    }

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

软1802黄汨文

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-角谷猜想（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

数据结构-图的遍历——DFS深度优先搜索-题解（好像木有JAVA代码的，那我就补充一下

评论区

精彩推荐

C二级辅导-计负均正（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

简单的a+b （C语言代码）

整数分类 oj上总是wrong answer

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

软1802黄汨文

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-角谷猜想 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

数据结构-图的遍历——DFS深度优先搜索-题解（好像木有JAVA代码的，那我就补充一下

评论区

精彩推荐

C二级辅导-计负均正 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

简单的a+b （C语言代码）

整数分类 oj上总是wrong answer

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

母牛的故事（C语言代码）

用筛法求之N内的素数。（C++代码）

C语言训练-角谷猜想（C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

Tom数（C语言代码）

C二级辅导-等差数列（C语言代码）