I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double loops for doing this:
for all u in G1
for all v in G2
if u.label == v.label then
do something here
end if
end for
end for
Now the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available?
I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism_problem). But here I am not trying to find out if the two graphs are isomorphic.
Is there a better/more efficient approach for doing this?
do something
? The answer will depend on these two. For instance, if each label is a single bit anddo something
isprint u,v
, then there's no asymptotically faster solution, as you need to print $\Theta(n^2)$ lines of output no matter what. Have you considered using a hash table to hash vertices by label, or sorting vertices by label? $\endgroup$ – D.W.♦ Oct 5 '15 at 15:45