Cormen Edition 3 Exercise 22.1 Question 4 (Page No. 593)

Question

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.

Answer 1

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
    let Adj'[1..|V|] be a new adjacency-list
    let M be |V| × |V|
    for each vertex u ∈ G.V
        for each v ∈ Adj[u]
            if M[u, v] == Ø && u != v
                M[u, v] = true
                INSERT(Adj'[u], v)