图的深度优先搜索-求解迷宫解空间

1.原理描述：
  给定图G的初始状态是所有顶点均未曾访问过，在G中任选一顶点V为初始出发点(源点、根结点)。
则描述如下：首先访问出发点V，并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点(子结点)W。
若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直到图中所有和源点V有路径相同的顶点(从源点
可达的顶点)均已被访问为止。若此图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复
上述过程，直到图中所有顶点均已被访问为止。

2.算法描述
  (1) 确定图的存储方式。
  (2) 设计搜索过程中的操作，其中包括为输出问题解而进行的存储操作。
  (3) 搜索到问题的解，则输出；否则回溯。
  (4) 一般在回溯前应该将结点恢复为原始状态，特别是在多解问题中。

3.一种实现：走迷宫问题。给定入口，求解搜索到出口的解空间。

package com.maozj.datastruct.graphic;

/**
 * create on 2010.05.15 说明：图的深度优先搜索
 * 
 * @author 毛正吉
 * @version v1.0
 * 
 * 
 */
public class DeepSearch {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		DeepSearch ds = new DeepSearch();
		ds.search(0, 0);
		System.out.println("\n"+ds.getTotal());
	}

	private int[][] maze = {
			{ 0, 0, 0, 0, 0, 0, 0, 0 },
			{ 0, 1, 1, 1, 1, 0, 1, 0 }, 
			{ 0, 0, 0, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 0, 0, 0, 1, 0 }, 
			{ 0, 1, 0, 1, 1, 0, 1, 0 },
			{ 0, 1, 0, 0, 0, 0, 1, 1 }, 
			{ 0, 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 1, 1, 1, 1, 0 } };
	
	private int[] fx = { 1, -1, 0, 0 };
	private int[] fy = { 0, 0, -1, 1 };
	private int total;

	public DeepSearch() {
		total = 0;
		// 入口坐标设置已走标志
		maze[0][0] = 3;
	}

	public void search(int i, int j) {
		int k, newi, newj;
		// 搜索可达的方格
		for (k = 0; k < 4; k++)
			if (check(i, j, k)) {
				newi = i + fx[k];
				newj = j + fy[k];
				// 来到新位置后，设置已走过标志
				maze[newi][newj] = 3;
				// 如到出口则输出，否则下一步递归
				if (newi == 7 && newj == 7) {
					Out();
				} else {
					search(newi, newj);
				}
			}
		// 标识走入死胡同的方格
		maze[i][j] = 2;
	}

	public void Out() {
		int i, j;
		for (i = 0; i < 8; i++) {
			System.out.println("");
			for (j = 0; j < 8; j++) {
				if (maze[i][j] == 3) {
					System.out.print("V");
					total++;
				} else {
					System.out.print("*");
				}
			}
		}
	}

	public boolean check(int i, int j, int k) {
		boolean bool = true;
		i += fx[k];
		j += fy[k];
		if (i < 0 || i > 7 || j < 0 || j > 7) {// 是否在迷宫内
			bool = false;
		} else if (maze[i][j] != 0) {// 是否可行
			bool = false;
		}
		return bool;
	}

	public int getTotal() {
		return total;
	}

}