DFS深搜思想:
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
1.递归实现方式
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | import java.util.Scanner;public class DFS{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][]arr = new int[n][n];//邻接矩阵 for(int i = 0; i < arr.length; i++){ for(int j = 0; j < arr[i].length; j++){ arr[i][j] = sc.nextInt(); } } int[] isVisted = new int[n];//记录站点是否走过 dfs(arr,isVisted,0);//深搜 } public static void dfs(int[][] arr,int[] isVisted,int v){ isVisted[v] = 1;//标记此站点已走过 System.out.print(v + " "); for(int i = 0; i < arr[v].length; i++){ //isVisted[i] == 0 该站点未走过 //arr[v][i] == 1 V点和I点是连通的 if(isVisted[i] == 0 && arr[v][i] == 1){ dfs(arr,isVisted,i);//访问下一节点 } } }} |
2.栈的实现思路
栈遵循先入后出的原则
解题思路：
(1)从起始站点X开始访问 入栈
(2)根据栈顶元素X寻找未访问过的邻接站点入栈
(3)如果未找到邻接站点则取出栈顶元素 出栈
(4)重复循环2-3步骤，当栈中元素为空时跳出循环
参考链接：https://blog.dotcpp.com/a/8450
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import java.util.Scanner;import java.util.LinkedList;public class DFS{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][]arr = new int[n][n];//邻接矩阵 for(int i = 0; i < arr.length; i++){ for(int j = 0; j < arr[i].length; j++){ arr[i][j] = sc.nextInt(); } } int[] isVisted = new int[n];//记录站点是否走过 LinkedList stack = new LinkedList(); stack.addFirst(0);//起始点 isVisted[0] = 1;//标记起始点已访问 System.out.print( 0 +" "); //栈不为空的时候循环 while(!stack.isEmpty()){ int v = stack.getFirst();//获取栈顶 boolean flag = true; //寻找以V为顶点的下一个邻接站点 for(int i = 0 ; i < arr[v].length; i++){ //isVisted[i] == 0 此站点没有被访问过 //arr[v][i]==1 表示 v点 和 i 点是连接的 if(isVisted[i]==0&&arr[v][i]==1){ stack.addFirst(i);//入栈 System.out.print(i +" "); isVisted[i] = 1;//标记此站点已走过 flag = false;//标记存在邻接站点 break; } } if(flag)stack.removeFirst(); } } } |
C#实现 https://blog.csdn.net/qq_50057017/article/details/123348717
9.9 分
4 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复