能否用BFS进行有向图环检测

Question

问题见标题

Answer 1

liuyubobobo 2020-10-31 12:17:43

可以呀。大多数能用 dfs 做的事情，bfs 都 ok。自己写代码试试看？

加油！：）

• 提问者 慕运维9331189 #1

  bobo老师，那个bfs做无向图的环检测，我知道怎么做。
  有向图的话，你讲的dfs用了onPath这样一个数组，表示这个节点是否在当前路径上。bfs我没想到这个思路怎么移植过来。
  我想的一个思路是，开一个path_num数组，每次取出队列头对应的节点后，在相邻节点入队时，给这些节点的path_num赋值，从取出节点的path_num值开始依次+1。
  当碰到 visited[w] && path_num[w] == path_num[v]时，就说明存在环。（v表示当前取出的节点，w表示相邻的节点）。
  
  慕课网的评论无法发图片。。。可能有图的话说的更清楚。
  
  想让bobo老师看看这个思路对不对，另外您还有没有更好的思路   ^_^

• 提问者 慕运维9331189 #2

  如果您觉得我表述的不够清晰，我可以再开一个问题，问题里面是可以添加图片的。

• liuyubobobo 回复 提问者 慕运维9331189 #3

  你单独开一个问题吧，我仔细看一下你的思路。谢谢：）

点开查看后面1条评论