So here's a simple graph.
We're going to start here with node number 2,
and we're going to set the depth there equal to 0.
And our goal is to find these depths for each of these vertices.
Originally, none of these are set.
We're just going to say that's the value for hasn't visited yet.
And we're going to begin by setting vertex number 2 to the value 0.
So we note that the furthest vertex away from node 2 is two hops away.
So the maximum depth here is 2, and we should expect that we should iterate twice.
So we're going to begin the algorithm by looking at all of these edges in parallel.
And what we're looking for is a pattern
where one of the vertices of these edges is going to have a depth value set,
and the other one does not.
And we're going to find that 3 edges have this particular quality.
So one of them is going to be the edge between 1 and 2.
We'll check and see.
The depth at vertex 2 is 0 and vertex 1 has not been visited yet.
So we'll set it equal to 0 plus 1, which is 1.
We'll do the same thing for this edge here between 2 and 3, okay?
We visited 2; its value was 0.
We haven't visited 3, so we set its value to be 1.
And this edge here, 2 and 6.
Now we complete the first iteration.
We visited every single edge
and run 6 threads in parallel to make this particular determination.
Now we begin our second iteration.
So now, again, what we're looking for is an edge
where the vertex value of one end of the edge has been set
and the other one has not yet been visited.
So we're going to find that's true for the other 3 edges.
So the edge between 0 and 1, we find that the depth at vertex number 1 is 1.
We find that vertex 0 has not yet been visited.
So we set its depth to 1 plus 1 equals 2.
And the same is going to be true for the edges between 3 and 4
and the edge between 5 and 6, okay?
Now we filled in a value for all of our vertices here,
and we're thus complete.
那么这是一个简单的图。
我们打算从节点数为2的这里开始,
然后我们把那里的深度设为0。
我们的目的是为这些顶点找到对应的深度。
原来,这些都没有设好。
我们只是打算这么说,那是用于未被访问的节点的值。
因此我们打算从设置顶点2的值为0开始。
那么,我们注意到,最远的顶点离节点2的距离是2个跃点。
所以,这里的最大深度值为2,而且我们应该希望我们应该迭代两次。
所以我们通过并行的方式观察所有这些边缘开始算法。
而且我们要找的是一种模式
这些边缘的顶点中有一个将有设定的深度值,
而另外一个还没有。
我们将发现这三个边缘具有这个特殊性质。
为此,其中一个将是一个介于1到2的边缘。
我们来检视一下。
顶点2的深度值是0,顶点1还没有被访问。
所以,我们将它设置为0+1,也就是1。
我们在2和3之间的边缘进行同样的设置,好吗?
我们访问了2,它的值是0。
我们还没有访问3,我们把它的值设置为1。
另外,这个边缘,2和6。
现在,我们完成了第一次的迭代。
我们访问了每个边缘,
然后运行6个并行的线程,来完成这个特定的测算。
现在我们开始我们第二次迭代。
现在,再一次,我们要寻找的是这样一个边缘,
在那里这个边缘的一端的顶点值已经被设定,
另外一个顶点还没有被访问。
所以,我们将找到符合条件的其他三个边缘。
所以这个边缘介于0到1,我们发现顶点1的深度为1。
我们发现顶点0还没有访问到。
为此我们将它的深度设置为1+1等于2。
另外,这种情况也适用于3和4之间的边缘,以及
5和6之间边缘,对吧?
现在我们在这儿来填写一下所有这些顶点的值。
这样我们就完成了。