DFS和BFS

[a02418wang]

唔，并不知道写啥，就写写最基础的东西吧。(其实数据结构应该有讲这种东西？
DFS和BFS分别是深度优先搜索与广度优先搜索，顾名思义即为搜索算法

适用范围：
DFS主要适用于寻找最长路径，比方说从某个节点出发，能到的最远的节点这种。
BFS适用于最短路径，比方说从某个节点出发，如何最快走进死胡同这种。。
值得注意的是，两种搜索方法的差异不仅仅是在优先度上面，它们的搜索结果本身是不一样的。
比方说有ABC三个节点。
A->B
B->C
A->C

深度优先搜索得到的AC距离是2，而广度优先搜索得到的AC距离是1，就这样。

实现：
BFS主要通过遍历访问所有相邻节点，再对所有被访问的节点重复上一步以实现。
很明显，因为要遍历访问所有节点，因此你刚访问完一个节点，就得去访问下一个，不能马上对该节点的相邻节点进行遍历访问，所以通常用先进先出的堆以实现。

另外，为了保证是最短路径(以及避免死循环)，会维护一个表以保证不重复访问。

queue.push(origin_node)
while(cur_node=queue.shift)//取出队列的第一个值
  cur_node.next_nodes.each do |visiting_node| //对cur_node的每个相邻节点进行访问，当前的被访问节点为visited_node
    //只要当前节点还没被访问，就加入队列,它离原点的距离比cur_node多一。
    next if visiting_node.visited?
    visiting_node.visited? = true
    visiting_node.length_to_origin = cur_node.length_to_origin + 1
    queue.push(visiting_node)
  end
end

就这样。搜索完成后，你只要访问任意一个节点的length_to_origin属性，就知道其与原点的最短距离了。
当然，不一定要完全搜索，比方说你只想找一个最短的死胡同，你只要在while下一行加一个
return cur_node unless cur_node.next_nodes (unless condition = if !condition)

比方说该代码应用于之前说的三节点情况时时，假设origin_node是A。origin_node.length_to_origin = 0。
那么(A,B,C) => (0,1,1)

DFS在很多意义上都与BFS正好相反
BFS先访问完再挨个遍历
DFS则是挨个访问并遍历

BFS的计数是以原点为基准，这样可以保证由近到远进行遍历
DFS则是以终点作为基准，保证其储存的是每个点离最远终点的距离

由于BFS要维持visited?(虽然我的代码中把它当节点的自带属性了，但通常是用一个数组来维护的
还有那些已访问但待遍历的点，
所以迭代比较自然

而DFS则由于要从终点从后往前算，递归比较自然。

BFS中起点很重要，不同的起点整个结果完全不一样，
DFS中起点是浮云，甚至就是要把所有的节点都作为起点遍历一次才保证完成

先上结构。
比方说之前说的三节点结构，应表示为：

(define a (delay (list b c)))
(define b (delay (list c)))
(define c (delay null))

(define l (list a b c))

其中a,b,c是节点，l是储存所有节点的表
然后是DFS实现

(define (DFS-l l)
  (define (DFS-n n)
    (define next_nodes (force n))
    (if (null? next_nodes)
        0
        (+ 1 (apply max (map DFS-n next_nodes)))))
  (map DFS-n l))

当然这十分低效，实际写的时候应当加上缓存。
就是在把在完成(+1 ...)那行代码后缓存当前节点的值

唔，那么运行 (DFS-l l)的结果是(2 1 0)
显然与BFS的(0 1 1)有明显差别。。
其差别如上文所说，就是AC之间的距离。

唔，DFS和BFS和冒泡算法类似，本身只是一个非常简单的思路，但实际运用中往往只是算法中的一个中间步骤，其实际代码肯定是要根据需求灵活改动的。

网上的代码各种i,j,k看的我一愣一愣的，所以自己写了一下。。写完才发现。。好像也好不到哪去。。
还是伪代码好懂啊。。
另外BFS的代码我自己比较懒没跑过的＝ ＝
有错误欢迎指出

[SihangWu]

BFS实现，第一个长代码上面第三行，"所以通常用先进先出的堆以实现。"
拼音错字？应该是队列吧

[a02418wang]

唔，你理解为队列也是没有任何问题的。。