算法:图的遍历(bfs+dfs)

图的深度优先遍历

这阵子有关搜索的题见的比较多，所以趁今天脑袋清醒，想来总结一下图遍历算法的实现过程

例子: 城市的遍历

给定城市的数量n，城市编号(1~n)，城市之间的连接情况，起点城市编号，遍历所有城市

图是一种经典的数据结构，倘若对图进行搜索，最直接的方法就是使用回溯法，为了防止遍历重复的城市，需要开一个数组用来维护已访问的城市，

//递归搜索法
	static void dfs(int begin,int[][] map,int[] book,int sum,int total) {
		System.out.println(begin); //输出当前城市序号
		sum++;
		if(total == sum) {
			return; //sum等于城市数量时，全部遍历完成
		}
		int size = map.length;
		for(int i=1;i<size;i++) {
			if(map[begin][i]==1 && book[i]==0) {
				book[i] = 1;//城市已经访问，book数组标记为1
				dfs(i,map,book,sum,total);//开始去搜索下一座城市
			}
		}
	}

但是，考虑到递归调用的是系统的栈，构建图的领接矩阵一旦大起来，执行效率就会很差，第二种方法则进行了优化，使用了一个局部栈来保存城市序号，得以优化

//调用局部栈
	static void DFS(int cur,int[][] map,int[] book,int n) {
		Stack<Integer> S = new Stack<Integer>();
		boolean flag = true;//判断是否要回溯
		S.push(cur);
		System.out.println(S.peek());
		while(!S.isEmpty()) {
			if(!flag) {
				S.pop();//如果当前城市没有领接城市，或者有领接城市但是领接城市已经访问，则弹栈
				if(S.isEmpty()) {
					break;
				}
			}
			int val = S.peek();
			flag = false;
			for(int i=1;i<=n;i++) {
				if(map[val][i]==1 && book[i]==0) {
					S.push(i);//有没有访问的城市，就压栈
					book[i] = 1;//标记已经访问
					System.out.println(i);//输出城市编号
					flag = true;
					break;
				}
			}
		}
	}

同样的，搜索问题还可以用广度优先搜索算法实现，这里使用一个队列

//BFS广度优先搜索
	static void BFS(int cur,int[][] map,int[] book,int n) {
		Queue<Integer> Q = new LinkedList<Integer>();
		//begin here
		Q.add(cur);
		boolean flag = true;
		System.out.println(cur);
		while(!Q.isEmpty()) {
			if(!flag) {
				Q.poll();
				if(Q.isEmpty()) {
					break;
				}
			}
			int val = Q.peek();
			flag = false;
			for(int i = 1;i<=n;i++) {
				if(map[val][i]==1 && book[i] == 0) {
					Q.add(i);
					System.out.println(i);
					book[i] = 1;
					flag = true;
					break;
				}
			}
		}
	}

Main函数

public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("城市个数");
		int n = in.nextInt();
		int[][] map = new int[n+1][n+1];
		int[] book = new int[n+1];
		int sum = 0;
		//初始化地图
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				map[i][j] = i==j?0:Integer.MAX_VALUE;
			}
		}
		System.out.println("互相连通的城市有多少组");
		int m = in.nextInt();
		System.out.println("输入连通城市序号");
		for(int i=1;i<=m;i++) {
			int t1 = in.nextInt();
			int t2 = in.nextInt();
			map[t1][t2] = 1;
			map[t2][t1] = 1;
		}
		System.out.println("起点序号:");
		int start = in.nextInt();
		book[start] = 1;
		long begin = System.nanoTime();
//		dfs(start,map,book,sum,n); //递归法
		DFS(start,map,book,n); //使用栈
		long end = System.nanoTime();
		System.out.println("遍历时间:"+(end-begin));
	}

经过运行，发现数据一大，递归法效率确实很低，看来以后要谨慎使用递归了
测试用例:
*城市个数
11
互相连通的城市有多少组
13
输入连通城市序号
5 6
1 5
1 2
2 3
2 11
9 11
1 9
10 9
4 10
4 8
1 7
1 4
11 9
起点序号:
9