Error result while performing BFS algorithm

Question

Error result while performing BFS algorithm

Closed this issue 5 years ago · 3 comments

Error result while performing BFS algorithm.
Input data :# nodes: 3997962 ===> output : found_vertices = 1655427.
Input data :# nodes: 2394385 ===> output : found_vertices = 1
Why is the number of input nodes inconsistent with the number of output nodes?

Answer 1 · 2019-04-05T09:07:13.000Z

I am not sure I fully understand what you mean. Can your give more details?

Answer 2 · 2019-04-07T15:01:45.000Z

[root@hw073 GeminiGraph]# ./toolkits/bfs /home/renrui/graph-datasets/data/email-EuAll.txt.bin 265214 1
active(0)>=1
active(1)>=129372
active(2)>=19139
active(3)>=6
exec_time=0.014675(s)
found_vertices = 148518

Answer 3 · 2019-04-08T01:29:54.000Z

Well, the found_vertices in the output of BFS is the number of vertices that can be reached from the root vertex, which doesn't necessarily equal |V|.