DFS深度优先搜索 两种实现方式(递归，栈)

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