CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
digital_revenant
digital_revenant

Reputation: 3324

Algorithm to convert adjacency list of a multigraph to an equivalent undirected graph

We are given the adjacency list for a multigraph, G = (V, E) and need to find an O(V + E) algorithm to compute the adjacency list of an equivalent undirected graph.

So far, I have thought of having an array of size |V| so as to mark the vertices that have been encountered at least once in adj[u], and thus preventing duplicates. The array is reset before traversing each adj[u]. But, I want to know if there exists a better algorithm for this that does not use extra space. Please suggest.

Upvotes: 0

Views: 1946

Answers (4)

Ami
Ami

Reputation: 195

Encountered the same problem.

After thinking, I would like to suggest a quick little fix for your solution. As @sunnytheit mentioned - between each two iterations between two different adjacency lists, you've got to reset the indicating-array. This actions takes you $\Theta(|V|)$ indeed (In total summing up into polynomial runtime complexity). To fix it, you might use a stack parallerly with the array.

Once you reach a vertex in current adj-list, you firstly check whether it's located in array, if it does, you continue to the next neighbor. If it does not, you push it onto the stack and update the indicating value in the array.

When you finish running on the current adj-list, you would like to pop the elements you met on that adj-list, and for each value you would like to reset the corresponding value in the array.

Totally, it sums up to twice passing the edges of the graph. So, finally the runtime complexity would be $\Theta(|V|+|E|)$ as asked.

Remark: you can save up the additional space by using a BST of some sort instead of the array - but you would have to analyze its influence on the runtime complexity.

Upvotes: 1

sunnytheit
sunnytheit

Reputation: 136

For reference it should be noted that technically, every time array is reset it uses O(V) time. Array creation is not technically free since it is created with random pointers with no guarantee of what those values will be.Thus it requires a single pass to actually initialize them 0 or null. Thus the run time becomes O(V^2) for your proposed algorithm.

I know this question has been resolved by now, but this fact should be noted.

Upvotes: 2

adrianN
adrianN

Reputation: 417

You could use a unordered set datastructure to improve from O(n) extra space to O(max number of neighbors) by only checking that no neighbor is added twice to the adjacency list.

Upvotes: 0

amit
amit

Reputation: 178461

If you want to achieve O(V+E) time complexity, there is no better algorithm, because this is basically a variation of the element distinctness problem, which can be solved by sorting in O(nlogn), or by using O(n) extra space in O(n).

So, to achieve O(V+E) time, your algorithm is optimal (in terms of big O notation)

Upvotes: 1

Related Questions