CODEWITHSUNDEEP
algorithmgraphadjacency-list
tarski
tarski

Reputation: 330

Given an adjacency list for multigraph, compute adjacency list for equivalent (simple) undirected graph in O(|V|+|E|) time

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 (simple) undirected graph.

I found the following solution in another post (it was part of the question section hence my repost):

"[H]aving 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]."

Forgive my ignorance, but I'm not sure how this is O(|V| + |E|). What is the cost of resetting a length |V| array |V| times?

Thank you.

Upvotes: 3

Views: 1055

Answers (1)

Sorin
Sorin

Reputation: 11968

You don't need to actually reset the array.

Say the array stores int. A vertex is marked iff mark[u] == v where v is the index or id of the current vertex.

When you move to the next vertex the value of v changes and all the entries in the array will evaluate to false without having to change the values in the array.

Upvotes: 2

Related Questions