Assume we have Graphs $G$ and $H$ and $V(G) = V(H)$, where $V$ is a set of vertices. What would be the algorithm to find out if these graphs are identical? The time boundary for this task is $\mathcal{O}(m+n)$ ($m$ and $n$ are not specified but I assume $m$ is $|E(H)|$ and $n$ is $|V(H)|$ where $E$ is a set of edges).
Graphs are not directed nor edge-weighted.
In my opinion the time boundary says us that the algorithm should be based on $DFS$ or $BFS$. In my solution I use $DFS$ to count vertex degree and check if vertex degree in graph $G$ is the same as this vertex degree in $H$. I'm not sure if this is the correct way of solving the problem, thus I am asking you – is it?
EDIT:
Ok, so there seems to be a lot of confusion as what 'identical' graph means… So I was not entirely sure at the time I asked the question, but now I know that I need to just check if the sets of edges of these graphs are equal. I still don't know how to do that in $\mathcal{O}(m+n)$ time though (assuming that graphs are stored as adjacency lists).
Best Answer
Your idea to use DFS or BFS is correct; however, checking for matching degree sequences will not be enough, in general. The reason for this is that non-isomorphic graphs can have matching degree sequences.
To have a better idea of the solution, I think it's best to clearly define what it means for graphs $G$ and $H$ to be "identical". The concept of graph isomorphism is probably what you want here. Two graphs $G$ and $H$ are said to be isomorphic if there exists a bijection $f:V(G) \rightarrow V(H)$ such that for all vertices $u, v$ that are adjacent in G, we have that $f(u)$ and $f(v)$ are adjacent in $H$. Such a function $f$ is said to be a graph isomorphism. Since you stated that $V(G) = V(H)$, I assume that you already have some bijection $f$ and you are wanting to test if $f$ is a graph isomorphism.
To check that $f$ is a graph isomorphism, for each vertex $v$, we can examine each of its neighbors $u$ in $G$ and check that $f(v)$ and $f(u)$ are adjacent in $H$. This can be done in $O(n+m)$ time using BFS.
Note that your problem, deciding whether a bijection $f:V(G) \rightarrow V(H)$ is a graph isomorphism, is much easier than trying to determine whether $G$ and $H$ are ismorphic; that is, whether a graph isomorphism $f$ exists. The complexity of graph isomorphism testing is actually an active area of research. If you are looking for software to do this, I recommend nauty, written by Brendan McKay.