深度优先遍历(DFS)

<img src="http://img.blog.csdn.net/20160315122918036?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" align="bottom" alt="" />

public class deepTravel {

public static void main(String[] args) {
//顶点之间的关系(图),1表示连接，0表示不连接
int[][] a={
{0,1,1,1,0},
{1,0,1,1,1},
{1,1,0,0,0},
{1,1,0,0,0},
{0,1,0,0,0}
};

//记录染色信息
int[] color = new int[a.length];

//调用深度优先遍历函数
deeptravel(a,color,0);
}

private static void deeptravel(int[][] a, int[] color, int i) {
//输出当前遍历到的顶点
System.out.println(i);
//对当前的顶点进行染色
color[i]=1;
//遍历第i行的顶点
for(int k = 0;k<a[i].length;k++){
//判断当前顶点是否与第i行的第k个顶点是否连接
//同时判断第i行的第k个顶点是否染色，也就是是否遍历过
if(a[i][k] == 1 && color[k] == 0){
//两个条件成立，则递归顶点
deeptravel(a,color,k);
}
}

}

}

例子：迷宫问题

import java.util.HashSet;
import java.util.Set;

public class maze {
private char[][] data;
private Pos entry;
private Pos exit;
private Set solve = new HashSet();

class Pos {
int i;
int j;

public Pos(int x, int y) {
i = x;
j = y;
}

public int hashCode() {
return i * 1000 + j;
}

public boolean equals(Object x) {
if (x instanceof Pos == false) {
return true;
}
Pos p = (Pos) x;
return p.i == i && p.j == j;
}

}

private boolean go(Pos cur, Set path) {
if (cur.equals(exit))
return true;
path.add(cur);

Pos[] t = { new Pos(cur.i, cur.j - 1),// 上
new Pos(cur.i, cur.j + 1),// 下
new Pos(cur.i - 1, cur.j),// 左
new Pos(cur.i + 1, cur.j) // 右
};

for (int i = 0; i < t.length; i++) {
try {
if (data[t[i].i][t[i].j] != '#' && path.contains(t[i]) == false) {
if (go(t[i], path)) {
solve.add(cur);
return true;
}
}
} catch (Exception e) {
}
}

return false;
}

private void go() {
Set path = new HashSet();
solve = new HashSet();
go(entry, path);
}

private void show() {
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
char c = data[i][j];
if (c == '.' && solve.contains(new Pos(i, j)))
c = 'x';
System.out.print(c + "");
}
System.out.println();
}
}

private void getStdInput() {
String[] x = { "####B#######", "####....####", "####.####..#",
"#....#####.#", "#.#####.##.#", "#.#####.##.#", "#.##.......#",
"#.##.###.#.#", "#....###.#.#", "##.#.###.#.A", "##.###...###",
"############" };

data = new char[x.length][];
for (int i = 0; i < data.length; i++) {
data[i] = x[i].toCharArray();
for (int j = 0; j < data[i].length; j++) {
if (data[i][j] == 'A')
entry = new Pos(i, j);
if (data[i][j] == 'B')
exit = new Pos(i, j);
}
}
}

public static void main(String[] arg) {
maze a = new maze();
a.getStdInput();
a.show();
a.go();

System.out.println("----------------");
a.show();
}

}