The Gateway to Computer Science Excellence
0 votes
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.
in Algorithms by Boss (41.9k points) | 31 views

1 Answer

0 votes
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)
by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,597 answers
195,835 comments
102,122 users