Given two S and T vertices in an undirected graph G I was thinking on the best way to find their common neighbors. I was thinking about this:

Map all the neighbors of S in a hash table in a size of V. The hash table simply take each vertex and put him in his place in the table based on his index. Then I go over all the neighbors of T and put him in the same hash table and if one of them get to a place that is already taken than this is the common vertex. the complexity for this algorithm is O(V+E).

Is there any better algorithm?

  • $\begingroup$ It all depends on what data structure you are using to store the graph in the computer in the first place. $\endgroup$ – Gerry Myerson Feb 28 '19 at 12:26

If you can iterate effectively over your neighbors, you could say the complexity of your algorithm is even better, namely $O(\deg(S)+\deg(T))$. If not, you can still bound it by $O(V)$ unless you have a multigraph.

There might be better algorithms with regard to memory, because your algorithm requires $O(\deg(S) + \deg(T))$, for example if you store the graph as sorted (by id's) neighborhood lists, then you can just iterate over them in parallel with $O(1)$ memory and same running time.

Also, there might be some other cases which work better for special classes of graphs. For example, depending on you underlying structure for the graph, you can optimize for the cases where it happens frequently that $\deg(S) \ll \deg(T)$ or $\deg(T) \ll \deg(S)$, by iterating over the smaller set and looking it up in the larger. Please remember, this is a special case, so normally it would not (should not) matter.

I hope this helps $\ddot\smile$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.