深度搜索的概念：搜索连通图的经典递归算法（遍历所有的顶点和边）和Tremaux搜索类似，但描述起来更简单。 要搜索一幅图，只需用一个递归方法来遍历所有顶点。在访问其中一个顶点时： ‰

  1. 将它标记为已访问； ‰
  2. 递归地访问它的所有没有被标记过的邻居顶点。

Search API 的一种实现使用了这种方法，它使用一个 boolean 数组来记录和起点连通的所有顶点。递归方法会标记给定的顶点并调用自己来访问该顶点的相邻顶点列表中所有没有被标记过的顶点。如果图是连通的，每个邻接链表中的元素都会被检查到。 深度搜索举例
用深度优先算法求两点之间的最短路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.Scanner;

public class dfs {
    public static int min=99999;//存储最短路径
    public static int[] book=new int[101];//存储已经走过的点
    public static int n;//目标点
    public static int[][] e=new int[101][101];//存储二维数组

    //cur为当前所在点的编号，dis是当前走过的路程
    void dfs(int cur, int dis){
        //如果当前路程已经大于之前的最短路程，则结束尝试
        if(dis>min)
            return;
        if(cur==n){
            if(dis<min){
                //更新存储路径
                min=dis;
                return;
            }
        }

        //从0点一直查找到n点
        for(int j=0;j<=n;j++){
            if(e[cur][j]!=99999&&book[j]==0){
                book[j]=1;//标记当前点在已有路径中
                dfs(j,dis+e[cur][j]);
                book[j]=0;//取消对该点的标记
            }
        }
    }
    public static void main(String[] args) {
        int a,b,c,m;
        Scanner kb=new Scanner(System.in);
        n=kb.nextInt();
        m=kb.nextInt();

        //初始化二维数组
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                if(i==j)
                    e[i][j]=0;
                else
                    e[i][j]=99999;
            }
        }

        /**
         * 读取两点编号和两点间距离，分别为
         * a b c
         */
        for(int i=0;i<=m-1;i++){
            a=kb.nextInt();
            b=kb.nextInt();
            c=kb.nextInt();
            e[a][b]=c;
        }
        book[0]=1;
        dfs t=new dfs();
        t.dfs(0,0);
        System.out.println();
        System.out.println(min);
    }
}

参考资料： 《算法 第四版》