BFS与DFS

1.什么是BFS,DFS

BFS宽度优先搜索.一层一层搜索.把每行的结果存入到队列中,然后遍历求下一层.
DFS深度优先搜索.第一次先到达最深,类似于栈的操作,然后弹起找完的一个节点找这个节点的下一层.
其实两种算法都是全局的遍历,时间复杂度一样的.但空间复杂度DFS小跟多.O(n)n为图的深度,BFS的空间复杂度是跟时间复杂度一样.指数级别.当然DFS肯定也是有缺点的,一个就是要用到递归.可能会因为栈的深度不够,堆栈溢出oom;而且宽度优先的话,可以搜索最短路径

2.例子:求二叉树最小深度

public int getMinDeep(TreeNode treeNode) {
        List<TreeNode> curNodes = new LinkedList<>();
        if (treeNode != null) {
            curNodes.add(treeNode);
        } else {
            return 0;
        }
        int path = 1;
        while (curNodes.size() > 0) {
    //每层用list存储,每次遍历当前层
            List<TreeNode> tempNodes = new LinkedList<>();
            for (TreeNode node : curNodes) {
    //遇到一个没有子节点了,则为最短路径
                if (node.left == null && node.right == null) {
                    return path;
                }
                if (node.left != null) tempNodes.add(node.left);
                if (node.right != null) tempNodes.add(node.right);

            }
            path++;
            curNodes = tempNodes;
        }
        return path;
    }

当然上面方式做的效率不高:下面快一些.leetcode中是0ms,上面方法用了2ms;

public int getMinDeep(TreeNode treeNode) {
        if (treeNode == null) return 0;
    //初始化一个深度,有节点则为1
        return findMinPath(treeNode, 1);
    }

    int findMinPath(TreeNode node, int deep) {
    //左右都为空,返回当前路径
        if (node.left == null && node.right == null) {
            return deep;
        }
    //左边为空,找到右边最短路径
        if (node.left == null) {
            return findMinPath(node.right, deep + 1);
        }
    //右边为空,找到左边最短路径
        if (node.right == null) {
            return findMinPath(node.left, deep + 1);
        }
    //都不为空,返回左右最短路径
        return Math.min(findMinPath(node.right, deep + 1), findMinPath(node.left, deep + 1));
    }

3.实际遇到的一个问题.

场景: 一个电商系统.我们有各种活动,同时不同活动有不同优惠券.一个活动只能用一张优惠券,一张优惠券也只能用于一个活动.求最优匹配

例如活动A选择了券B;则券B虽然与活动C匹配优惠8,但其不能再被使用;
尝试过用动态规划.但没写出来.感觉是不可行的.最终解决是:在时间复杂度差不多的时候,采用DFS,解决了内存问题.但同时,因为时间复杂度实在是太高.为N!N为行和列中较大数;确实在深度到一定的时候无法计算,只能用贪心算法简单进行计算.
附代码:

public class OptimalCoupon {
    public static long count;
    private double[][] data;
    private int rows;
    private int cols;
    private double maxValue;
    private int[] maxResArray;
    private int[] index;
    boolean[] indexSign;

    public double getMaxValue() {
        return maxValue;
    }

    public OptimalCoupon(double[][] data) {
        // 二维数组,数据源.算法中类型用double
        this.data = data;
        //列数
        this.rows = data.length;
        //行数
        this.cols = data[0].length;
        //最大优惠金额
        this.maxValue = 0;
        //行的坐标数组,数组下标对应列
        this.maxResArray = new int[rows];
        this.index = new int[rows];
        //boolean数组记录已用的列
        this.indexSign = new boolean[cols];
    }

    public int[] getOptimalColumn() {
        getRes(0, 0);
        return this.maxResArray;
    }

    public void getRes(int deep, double curRes) {
        //到了最后一层
        if (deep == rows - 1) {
            //循环最后一行
            for (int i = 0; i < cols; i++) {

                //没用过
                if (!indexSign[i]) {
                    count++;
                    curRes += data[deep][i];
                    //坐标结果集 有row个数,每个数代表每row的clo index
                    // deep = actCoupons.length - 1 也就是 row - 1
                    if (curRes > maxValue) {
                        maxValue = curRes;
                        index[deep] = i;
                        copyToRes(index, maxResArray);

                    }
                    curRes -= data[deep][i];
                }
            }
        } else {
            // 不是最后一层,取上能取到的最小的index,然后继续往下一层
            for (int i = 0; i < cols; i++) {

                //假如没有使用这个index
                if (!indexSign[i]) {
                    count++;
                    //使用
                    indexSign[i] = true;
                    index[deep] = i;
                    //curRes + actCoupons[deep][i] 当前取值
                    getRes(deep + 1, curRes + data[deep][i]);
                    //下一层使用后,恢复
                    indexSign[i] = false;
                }
            }
        }
    }


    void copyToRes(int[] curRes, int[] res) {
        for (int i = 0, len = curRes.length; i < len; i++) {
            res[i] = curRes[i];
        }
    }
}