{"action":"opened","issue":{"url":"https://api.github.com/repos/100steps/Blogs/issues/21","repository_url":"https://api.github.com/repos/100steps/Blogs","labels_url":"https://api.github.com/repos/100steps/Blogs/issues/21/labels{/name}","comments_url":"https://api.github.com/repos/100steps/Blogs/issues/21/comments","events_url":"https://api.github.com/repos/100steps/Blogs/issues/21/events","html_url":"https://github.com/100steps/Blogs/issues/21","id":150723196,"number":21,"title":"DFS和BFS","user":{"login":"a02418wang","id":18643487,"avatar_url":"https://avatars.githubusercontent.com/u/18643487?v=3","gravatar_id":"","url":"https://api.github.com/users/a02418wang","html_url":"https://github.com/a02418wang","followers_url":"https://api.github.com/users/a02418wang/followers","following_url":"https://api.github.com/users/a02418wang/following{/other_user}","gists_url":"https://api.github.com/users/a02418wang/gists{/gist_id}","starred_url":"https://api.github.com/users/a02418wang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/a02418wang/subscriptions","organizations_url":"https://api.github.com/users/a02418wang/orgs","repos_url":"https://api.github.com/users/a02418wang/repos","events_url":"https://api.github.com/users/a02418wang/events{/privacy}","received_events_url":"https://api.github.com/users/a02418wang/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-04-25T01:34:12Z","updated_at":"2016-04-25T01:34:12Z","closed_at":null,"body":"唔，并不知道写啥，就写写最基础的东西吧。(其实数据结构应该有讲这种东西？\r\nDFS和BFS分别是深度优先搜索与广度优先搜索，顾名思义即为搜索算法\r\n\r\n适用范围：\r\nDFS主要适用于寻找最长路径，比方说从某个节点出发，能到的最远的节点这种。\r\nBFS适用于最短路径，比方说从某个节点出发，如何最快走进死胡同这种。。\r\n值得注意的是，两种搜索方法的差异不仅仅是在优先度上面，它们的搜索结果本身是不一样的。\r\n比方说有ABC三个节点。\r\nA->B\r\nB->C\r\nA->C\r\n\r\n深度优先搜索得到的AC距离是3，而广度优先搜索得到的AC距离是2，就这样。\r\n\r\n实现：\r\nBFS主要通过遍历访问所有相邻节点，再对所有被访问的节点重复上一步以实现。\r\n很明显，因为要遍历访问所有节点，因此你刚访问完一个节点，就得去访问下一个，不能马上对该节点的相邻节点进行遍历访问，所以通常用先进先出的堆以实现。\r\n\r\n另外，为了保证是最短路径(以及避免死循环)，会维护一个表以保证不重复访问。\r\n\r\n\r\n    queue.push(origin_node)\r\n    while(cur_node=queue.shift)//取出队列的第一个值\r\n      cur_node.next_nodes.each do |visiting_node| //对cur_node的每个相邻节点进行访问，当前的被访问节点为visited_node\r\n        //只要当前节点还没被访问，就加入队列,它离原点的距离比cur_node多一。\r\n        next if visiting_node.visited?\r\n        visiting_node.visited? = true\r\n        visiting_node.length_to_origin = cur_node.length_to_origin + 1\r\n        queue.push(visiting_node)\r\n      end\r\n    end\r\n\r\n就这样。搜索完成后，你只要访问任意一个节点的length_to_origin属性，就知道其与原点的最短距离了。\r\n当然，不一定要完全搜索，比方说你只想找一个最短的死胡同，你只要在while下一行加一个\r\n`return cur_node unless cur_node.next_nodes\r\n`(unless condition = if !condition)\r\n\r\n比方说该代码应用于之前说的三节点情况时时，假设origin_node是A。origin_node.length_to_origin = 0。\r\n那么(A,B,C) => (0,1,1)\r\n\r\nDFS在很多意义上都与BFS正好相反\r\nBFS先访问完再挨个遍历\r\nDFS则是挨个访问并遍历\r\n\r\nBFS的计数是以原点为基准，这样可以保证由近到远进行遍历\r\nDFS则是以终点作为基准，保证其储存的是每个点离最远终点的距离\r\n\r\n由于BFS要维持visited?(虽然我的代码中把它当节点的自带属性了，但通常是用一个数组来维护的\r\n还有那些已访问但待遍历的点，\r\n所以迭代比较自然\r\n\r\n而DFS则由于要从终点从后往前算，递归比较自然。\r\n\r\nBFS中起点很重要，不同的起点整个结果完全不一样，\r\nDFS中起点是浮云，甚至就是要把所有的节点都作为起点遍历一次才保证完成\r\n\r\n先上结构。\r\n比方说之前说的三节点结构，应表示为：\r\n    (define a (delay (list b c)))\r\n    (define b (delay (list c)))\r\n    (define c (delay null))\r\n    \r\n    (define l (list a b c))\r\n\r\n其中a,b,c是节点，l是储存所有节点的表\r\n然后是DFS实现\r\n    (define (DFS-l l)\r\n      (define (DFS-n n)\r\n        (define next_nodes (force n))\r\n        (if (null? next_nodes)\r\n            1\r\n            (+ 1 (apply max (map DFS-n next_nodes)))))\r\n      (map DFS-n l))\r\n当然这十分低效，实际写的时候应当加上缓存。\r\n就是在把在完成(+1 ...)那行代码后缓存当前节点的值\r\n\r\n唔，那么运行 `(DFS-l l)`的结果是(2 1 0)\r\n显然与BFS的(0 1 1)有明显差别。。\r\n其差别如上文所说，就是AC之间的距离。\r\n\r\n唔，DFS和BFS和冒泡算法类似，本身只是一个非常简单的思路，但实际运用中往往只是算法中的一个中间步骤，其实际代码肯定是要根据需求灵活改动的。\r\n\r\n网上的代码各种i,j,k看的我一愣一愣的，所以自己写了一下。。写完才发现。。好像也好不到哪去。。\r\n还是伪代码好懂啊。。\r\n另外BFS的代码我自己比较懒没跑过的＝ ＝\r\n有错误欢迎指出"}}