广度/深度优先算法
程序员文章站
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();
}
}
}
上一篇: [图] 0 总结 - 记忆版
下一篇: Spring Bean的实例化
推荐阅读