DFS深搜思想:
(1)访问顶点v;
(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。
1.递归实现方式
参考代码:
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
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
0.0分
6 人评分
C语言训练-列出最简真分数序列* (C语言代码)浏览:505 |
简单的a+b (C语言代码)浏览:670 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:595 |
A+B for Input-Output Practice (C++代码)浏览:607 |
WU-输入输出格式练习 (C++代码)浏览:1079 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:467 |
母牛的故事 (C语言代码)浏览:715 |
Tom数 (C语言代码)浏览:725 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:566 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:662 |