深度优先搜索:订单重要吗?

2024-03-29 05:22:07 发布

您现在位置:Python中文网/ 问答频道 /正文

我用Python构建了一个深度优先搜索脚本,它正在遍历一个图。由于我没有最佳的排序算法,DFS的可视化看起来有点奇怪。我的意思是DFS获取节点的顺序是可重复的,但看起来很奇怪,因为在内部,我的graph类逐行读取文本文件,并将边(节点的元组)存储在一个集合中。你知道吗

当我开始我的算法时,它会扩展开始节点,寻找它的邻居,移动并继续这个过程,但是因为边是一个集合中的元组,有时DFS使用的第一个邻居是底部节点。下一次也许是对的,以此类推。这种方式打破了可视化,因为人类会说好的,如果我展开我的节点,收集邻域并加深/向右移动,我总是将图形加深到右侧,这意味着一些具体的顺序。你知道吗

我的问题是:解决方案仍然正确吗?在这种情况下,DFS是否应该向右走直线?图中的边必须排序,然后。。。你知道吗

我想实现这个图,就像它在数学中定义的那样。这就是为什么我用一组作为节点,用一组元组(vxv)作为边。你知道吗

每个状态的操作是:向上向下。只要没有墙/障碍物。你知道吗

示例

x: wall | s: start | g: goal | o: path taken by the DFS

xxxxxxxxxxxxxxxxxxxxxxxxx
x                       x
x                       x
x  s               goo  x
x  oo                o  x
x   o    ooooo     ooo  x
x   oo  oo   oooo  o    x
x    oooo       oooo    x
xxxxxxxxxxxxxxxxxxxxxxxxx

Tags: 脚本算法节点排序顺序过程可视化方式