YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Chinese, Simplified subtitles

← BFS尝试_第1个例子

Get Embed Code
2 Languages

Showing Revision 3 created 05/07/2013 by Michael Xiao.

  1. 那么这是一个简单的图。
  2. 我们打算从节点数为2的这里开始,
  3. 然后我们把那里的深度设为0。
  4. 我们的目的是为这些顶点找到对应的深度。
  5. 原来,这些都没有设好。
  6. 我们只是打算这么说,那是用于未被访问的节点的值。
  7. 因此我们打算从设置顶点2的值为0开始。
  8. 那么,我们注意到,最远的顶点离节点2的距离是2个跃点。
  9. 所以,这里的最大深度值为2,而且我们应该希望我们应该迭代两次。
  10. 所以我们通过并行的方式观察所有这些边缘开始算法。
  11. 而且我们要找的是一种模式
  12. 这些边缘的顶点中有一个将有设定的深度值,
  13. 而另外一个还没有。
  14. 我们将发现这三个边缘具有这个特殊性质。
  15. 为此,其中一个将是一个介于1到2的边缘。
  16. 我们来检视一下。
  17. 顶点2的深度值是0,顶点1还没有被访问。
  18. 所以,我们将它设置为0+1,也就是1。
  19. 我们在2和3之间的边缘进行同样的设置,好吗?
  20. 我们访问了2,它的值是0。
  21. 我们还没有访问3,我们把它的值设置为1。
  22. 另外,这个边缘,2和6。
  23. 现在,我们完成了第一次的迭代。
  24. 我们访问了每个边缘,
  25. 然后运行6个并行的线程,来完成这个特定的测算。
  26. 现在我们开始我们第二次迭代。
  27. 现在,再一次,我们要寻找的是这样一个边缘,
  28. 在那里这个边缘的一端的顶点值已经被设定,
  29. 另外一个顶点还没有被访问。
  30. 所以,我们将找到符合条件的其他三个边缘。
  31. 所以这个边缘介于0到1,我们发现顶点1的深度为1。
  32. 我们发现顶点0还没有访问到。
  33. 为此我们将它的深度设置为1+1等于2。
  34. 另外,这种情况也适用于3和4之间的边缘,以及
  35. 5和6之间边缘,对吧?
  36. 现在我们在这儿来填写一下所有这些顶点的值。
  37. 这样我们就完成了。