欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

广度/深度优先算法

程序员文章站 2022-03-03 11:21:42
...

广度优先算法

广度优先搜索breadth-first traverse(也称宽度优先搜索,缩写BFS)是连通图的一种遍历策略。一个最直观经典的例子就是走迷宫,我们从起点开始,找出到终点的最短路程,很多最短路径算法就是基于广度优先的思想成立的。

  • 这里用迷宫问题来解释(java代码)
待续

深度优先遍历算法

深度优先搜索算法(Depth-First-Search),是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。

  • 还是迷宫问题解释(java代码)
public class Depth
{
    static int count = 1;

    static int array[][] = {
                             {0, 1, 0, 0, 1},
                             {0, 0, 1, 0, 0}, 
                             {1, 0, 1, 0, 0}, 
                             {0, 0, 0, 0, 0}, 
                            };

    public static void main(String[] args)
    {
        play(0, 0);
    }

    // 算法具体逻辑实现类,2表示走过的路径
    public static void play(int row, int col)
    {
        if (row == array.length - 1 && col == array[0].length - 1)
        {
            show();
        }

        part(row, col + 1);
        part(row, col - 1);
        part(row + 1, col);
        part(row - 1, col);

    }

    // 部分逻辑业务处理类;
    public static void part(int row, int col)
    {
        if (check(row, col))
        {

            array[row][col] = 2;
            play(row, col);
            array[row][col] = 0;
        }
    }

    // 判断类
    public static boolean check(int row, int col)
    {

        if ((row >= 0 && row < array.length) && (col >= 0 && col < array[0].length))
        {
            if (array[row][col] == 0)
            {
                return true;
            }

        }
        return false;
    }

    // 这里仅简单显示,可根据需求具体调整
    public static void show()
    {
        System.out.println("第" + count + "种走法");
        count++;
        for (int i = 0; i < array.length; i++)
        {
            for (int j = 0; j < array[0].length; j++)
            {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
}