Comparing two graphs [closed]

Question

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?

Answer 1

A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.

This also assumes that the "do something"-bit doesn't change the label (and that the order of the "do something"s doesn't matter).