一种是一旦访问过就【不想要再次访问】,这种最常见,比如200 number of islands 或是785 is graph bipartite. 这种情况在遍历邻居们或者poll元素的时候添加visited都可以。
第二种是当层访问过以后【不想要再次访问】,比如 126 Word Ladder II 。这里需要使用一个hashmap记录node的层数,只有当前层数等于map记录的层数的时(也就是还在当层)才可以添加。因为我们只要添加距离最短的路径。一旦之前层添加过了,就没必要在更后面的层添加了。这种情况不同于第三种,这里的距离只与层数有关,随着层数逐步加一。而第三种情况对于每条edge的距离都不一样,所有要poll了才知道那条最短。
第三种是得到(也就是poll之后) 【不想要再次访问】, 这种情况往往用在PriorityQueue最短路径问题上。比如743 network delay time,当节点从PriorityQueue中poll出来后,说明能够到达改节点的最短路径已经获得,之后就不要再访问该节点了。这里只需要在poll出元素后先check是否visited,如果没有,则添加visited并进行下一轮操作。这种情况节点在哪一层添加的不重要,重要的是距离。也许第一层就加进PriorityQueue了,奈何这条路径距离太长,它就不是我们想要的。