Me and my friend have been working on a problem for school. We are traversing a graph with DFS and are counting the number of nodes in each given component. We get widely different results and have identified where the difference lies.
When going into the next recursion, my friend uses the syntax
componentSize = DFS_visit(nextNodeToVisit);
whereas I use
componentSize = 1 DFS_visit(nextNodeToVisit);
I originally thought these two were the same, so what is the difference? And which one should be used in our case?
CodePudding user response:
componentSize = DFS_visit(nextNodeToVisit);
means
componentSize = componentSize DFS_visit(nextNodeToVisit);
Compare that with
componentSize = DFS_visit(nextNodeToVisit) 1;
See the difference?
In general a <op>= b
means roughly the same as a = a <op> b
where <op>
an operator. (There is also a typecast of the LHS to the type of a
.)
And which one should be used in our case?
It is not clear which is correct. We would need to see the data structure and more of the algorithm.
CodePudding user response:
your friend is accumulating the size of each node,
while you are counting the nodes