I'm trying to understand the Breadth First Search complexity (work and span). For the case in the picture, I don't understand how line 9 works, and from that to calculate the Work & Span. Full BFS using set X and F as boolean sequence
X is set of visited vertices, F is frontier set (i.e. is the positive neighbor vertices because this is directed graph, not undirected, positive mean you can move from A -> B, but not B -> A).
Anyone explain how line 9 works ? I tried but got a different result with the W,S in the lecture note from professor. My question is how the N+G(F) work ?
For example: I have this graph, we are given 0 are the starting node.
The adjacent matrix:
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0
For the first iterator:
X = 0,0,0,0
F = 1,0,0,0
How they calculate N+G(F) now ? I tried but my way only lead to causing line 9 cost: W = |V|^2, S = 2. But the result for the while BFS is W = |V|^2 ??? (my way could create |V|^3 ! )
So this is my method: From the adjacent matrix. Each row I x with the boolean of that corresponding line in F -> each row result. Then I intersect these row results to have F'.
Thanks