On the left, we run F for each edge between the frontier and the unvisited vertices, whereas on the right F only runs once for each unvisited vertex.
This comment was marked helpful 0 times.
bosher
In the sparse version, we can see that an vertex will be pulled into the frontier by its in-neighbors, whereas in the dense version, all the vertices will try to put themselves into the frontier.
Sparse version is good for sparse graph because there will tend to be less out-neighbors for each vertices in a sparse graph. And therefore compute the new frontier will not use too much time.
However, in a dense graph, each vertex may have many out-neighbors, which makes computing the new frontier too expensive.
On the left, we run F for each edge between the frontier and the unvisited vertices, whereas on the right F only runs once for each unvisited vertex.
This comment was marked helpful 0 times.
In the sparse version, we can see that an vertex will be pulled into the frontier by its in-neighbors, whereas in the dense version, all the vertices will try to put themselves into the frontier. Sparse version is good for sparse graph because there will tend to be less out-neighbors for each vertices in a sparse graph. And therefore compute the new frontier will not use too much time. However, in a dense graph, each vertex may have many out-neighbors, which makes computing the new frontier too expensive.
This comment was marked helpful 0 times.