[数据结构与算法]【AU】深度优先搜索DFS（java实现）

深度优先搜索

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

import java.util.Scanner;

public class DFS {
	static int[][] grap;// 邻接矩阵
	static int[] isVist;// 辅助数组，记录该节点是否已经被访问
	static int n;// 图的节点个数
	static int k;// 图的边个数

	static void creatGrap() {// 创建邻接表
		Scanner s = new Scanner(System.in);
		System.out.println("输入点个数：");
		n = s.nextInt();
		System.out.println("输入边个数：");
		k = s.nextInt();
		grap = new int[n][n];
		isVist = new int[n];
		System.out.println("输入边信息：");
		for (int i = 0; i < k; i++) {
			int a = s.next().charAt(0) - 'A';// next()只能读取字符，不能读取空格等符号，
			int b = s.next().charAt(0) - 'A';// 将读取的字符转换为数字，方便二维数组的是使用；
			grap[b][a] = 1;
			grap[a][b] = 1;
		}
		// 输出邻接表
		System.out.println("输出邻接矩阵");
		System.out.print(" ");
		for (int i = 0; i < n; i++) {
			System.out.print(" " + (char) (i + 'A'));
		}
		System.out.println();
		for (int i = 0; i < n; i++) {
			System.out.print((char) (i + 'A') + " ");
			for (int j = 0; j < n; j++) {
				System.out.print(grap[i][j] + " ");
			}
			System.out.println();
		}

	}

	static void dfs(int from) {// 深度搜索 from代表起点
		isVist[from] = 1;
		System.out.print((char) (from + 'A') + " ");
		for (int i = 0; i < n; i++) {// 找到所有链接from的节点不断深入递归
			if (grap[from][i] != 0 && isVist[i] == 0) {
				dfs(i);

			}
		}
	}

	public static void main(String[] args) {

		creatGrap();// 创建邻接矩阵
		System.out.println("输出dfs顺序:");
		dfs(0);// 深度优先搜索
	}
}