31 views
Given an adjacency-list representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacency-list representation of the “equivalent” undirected graph $G’=(V,E’)$ , where $E’$ is consists of the edges in $E$ with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.
| 31 views

Create a new adjacency-list Adj of size |V| and an empty matrix M of size |V|^2  first. For each vertex u in the multigraph G, we iterably examine each vertex v of Adj[u].

•If M(u, v) == ∅, mark M(u, v) true, then add v to Adj[u]

•If M(u, v) == true, do nothing.

Since we lookup in the adjacency-list Adj for |V + E| times, the time complexity is O(V + E).

▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

EQUIVALENT-UNDIRECTED-GRAPH