3
$\begingroup$

Suppose we have a directed graph $G = (V,E$) represented with adjacency lists. Is it possible to convert $G$ into its undirected equivalent* $G'$, also represented with adjacency lists, in $O(|V|+|E|)$ time?

The obvious algorithm walks the adjacency list of each vertex $v$, and for each adjacent vertex $u$, inserts edges $(v,u)$ and $(u,v)$ into $G'$. The issue is duplicates. If $(u,v)$ happens to be in $G$ already, $(u,v)$ will be inserted into $G'$ twice: once when processing $v$'s adjacency list, and once when processing $u$'s. Assuming that a well-formed graph doesn't contain any duplicate edges, we would need to check $u$'s adjacency list to see whether it contains $v$ before performing the second insertion. But this check takes linear time in $|V|$, and we would need to perform this check for $O(|E|)$ edges, resulting in $O(|V|*|E|)$ time complexity.

*Terminology: by "undirected equivalent" of a digraph $G=(V,E)$, I mean the directed graph $G'=(V,E')$ such that

if $(v,u) \in E$ then $(v,u) \in E'$ and $(u,v) \in E'$ and
if $(v,u) \in E'$ then either $(v,u) \in E$ or $(u,v) \in E$.

$\endgroup$
5
$\begingroup$

If you perform the check at the end rather than throughout, it will be much faster.

Start by going over all edges, and for each edge $(i,j)$ add the edge $(j,i)$ to the adjacency list of $j$.

Now given the adjacency list of $i$, we want to remove duplicates. For that we use an array indexed by $V$, which is initialized to zero (we only need to initialize it once). Go over the list and count how many times you see each edge. Now go over the list a second time and only add the first occurrence of every edge. Finally, go over the list a third time to reset the array back to zero. In all, we do $O(1)$ work per edge.

One drawback of this algorithm is that the resulting adjacency lists aren't sorted, even if you started out with sorted ones. Here is a different algorithm which works in $O(|V|+|E|)$ time and maintains this invariant (assuming it holds originally). For each vertex $i$, compute the sorted lists $\{ j : (i,j) \in G \}$ and $\{ j : (j,i) \in G \}$. Then merge them and remove duplicates.

$\endgroup$
  • $\begingroup$ Clever - I kept wanting to convert to adjacency matrix form but just initializing the matrix would have taken $O(|V|^2)$ time. By reusing the same array, you can initialize in $O(|V|)$ time and then write the count of occurences and reset to all zeros in $O(E_i)$ time, where $E_i$ is the set of outedges from the $i$th vertex. That way you get $O(|V|+|E|)$ all together for the writes to your auxiliary array, and you get the constant-time lookup of an adjacency matrix representation without the quadratic initialization time. Cool! $\endgroup$ – Chad Feb 13 '17 at 21:14
2
$\begingroup$

Yuval's idea is probably better, but I'm posting mine anyway since it's a different approach.

First of all, observe that the only duplicates are those involving two nodes $u, v$ such that there is an edge "in both directions", in other words cycles of length two.

In the DFS forest of $G$, the only such edges are back-edges going from a node to its parent. This suggests an algorithm to solve your problem. Perform a DFS of $G$, adding each edge you find to $G'$, except for the edges $(u, v)$ such that $v = \pi(u)$.

$\endgroup$
  • $\begingroup$ Also a nice solution. Your $\pi$ stands for parent, yes? $\endgroup$ – Chad Feb 13 '17 at 21:28
  • $\begingroup$ @Chad Yes, exactly. $\endgroup$ – quicksort Feb 13 '17 at 22:42

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.