
Title:
BFS Try 1  An Example  Intro to Parallel Programming

Description:

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.