BFS学习笔记

完整的BFS包括以下要素

(1) 一个queue, 用于进行bfs遍历

(2) 每个node都有三个attribute: 1. visited or not tag; 2. parent(s), 有可能会有多个父亲; 3. length, length(child) = length(parent) + 1

(3) 对于1. visited or not tag更加细致的划分是一个node的状态其实有三种, 分别是discovered, undiscovered, processed: processed就是进入队列过, 而且已经被pop out队列的, undiscovered就是还没进入队列, discovered 就是进入了队列但是还没有被pop out这三种状态在某些情况下去需要细分, 一般node就两个状态visited or not足够了.

 

未完待续

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 28, 2013