楼主:
TKB5566 (我们的元首阿道夫希特勒)
2025-02-02 23:37:20以下是如何透过BFS(广度优先搜寻)来遍历整张图的大致流程
CODE我还不会写 先用纯文字表示用Java实作的流程:
0. 图本身要用Map<Integer,List<Integer>>型别的物件来表示。
图的每个节点都需要被记录是否被访问,这要用Set<Integer>型别的物件来表示。
不管是树还是图的BFS,都以QUEUE物件作为要被访问的节点的资料结构。
1. 选定一图的节点,节点在这里是以一个Integer型别之数字表示。
2. 该数字做为一开始访问的节点,被加入queue物件内(queue.add())、
接着将其取出(queue.poll())、印出数字、并将该数字加入set物件,表示已访问过。
3. 检查该数字对应的list是否有元素(也就是是否有值),若有的话则用循环将其
添加至queue、接着一样一一自queue取出、印出数字、再添加至set物件。
4. 从queue取出数字、印出数字、搜寻时否有连结的数字、添加至queue。
这串动作是只要queue不是空的就要重复做,
故“从queue取出数字、印出数字、搜寻时否有连结的数字、添加至queue”
必须包在while循环内。
5. 该循环执行完成,表示所有元素都被加入queue且被取出来访问,
故BFS执行完成。
6. 所以跟该资料结构搭配的算法,一样是回溯法。