Java 语言实现dfs算法

dfs的认识：

dfs即(depth-first-search)深度优先搜索。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题。

在图中，dfs从A点开始，假设先访问左边结点，后访问右边结点，在搜索时记住先前访问过得结点，并且不重复访问它们。那么将会得到一个访问序列： A, B, D, F, E, C, G。

dfs的java实现：

下面通过一个具体题目来了解一下它的实现。
题目：有1、2、3、4四个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？
扩展：输入不同数字的个数，组成数字的位数，输出所有无重复数字。
分析：由于不知道循环的嵌套次数，因此不能用简单的嵌套循环解决，考虑用dfs来解决。

代码：

设置sum记录总个数，a[]数组记录访问过的结点。

  static int sum=0;
  static int[] a = new int[101];

dfs的函数,n记录组成数的位数，m记录不同数字的个数,num记录满足条件的数。

   public static int dfs(int m,int n,int num)

终止的条件，结束时同时打印出num。

        if(n==0)
        {
            System.out.print(num+" ");
            sum++;
            if(sum%30==0)
                System.out.println();
            return 0;
        }

每一层对1到m进行循环，满足条件则跳入下一层，同时用a[n]记录下当前访问的结点。

        for(i=1;i<= m;i++)
        {   
            boolean flag = true;
            for(int j=n+1;j<=100;j++)  //判断i是否出现过
            {
                if(a[j]==i)
                {
                    flag = false;
                    break;
                }
            }
            if(flag)  //i没出现过，则进入dfs进入下一层
            {
                a[n] = i;
                num += i*(int)Math.pow(10,n-1);  //求num的过程
                dfs(m,n-1,num);
                num -= i*(int)Math.pow(10,n-1);  //递归返回后将num还原
            }
        }

主函数部分：

    public static void main(String[] args) {
        int num = 0;
        for(int i=1;i<=100;i++)
            a[i]=0;
        Scanner input = new Scanner(System.in);
        System.out.print("输入不同数字的个数：");
        int numDif = input.nextInt();
        System.out.print("输入组成几位数（位数小于数字个数）：");
        int digit = input.nextInt();
        System.out.println("组成的无重复数字"+digit+"位数分别为：");
        dfs(numDif,digit,num);
        System.out.println("\n共有："+sum+"个");
    }

dfs的总结：

dfs的思路不难理解，主要在于它的实现。在dfs实现的时候，要注意到及时去掉不满足条件的情况，即要对dfs进行剪枝操作，这样可以避免搜索的次数的增加。在dfs过程中牵扯到数的计算问题时，在回溯的时候，要注意将它还原。