wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Mutigraph to Undirected Graph
        
(Message started by: johny_cage on Nov 18^th, 2007, 3:25am)

Title: Mutigraph to Undirected Graph
Post by johny_cage on Nov 18^th, 2007, 3:25am

You have given an adjacency list representation of a multigraph 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' consists of the edges in E with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.

Title: Re: Mutigraph to Undirected Graph
Post by towr on Nov 18^th, 2007, 7:02am

[hide]Initialize the adjacency matrix to empty; then fill in all the edges, except those on the diagonal.[/hide]
Although, I suppose that presupposes direct mapping vertex to matrix column/row. I suppose a hashtable might be an option if the vertices aren't already numbered sequentially and we cant' attach a number to them.

Title: Re: Mutigraph to Undirected Graph
Post by johny_cage on Nov 18^th, 2007, 8:25am

but we have to find adjacency list, and if we use adjacency matrix then our algorithm will take O(|V|²) space complexity, and also to initialize it to 0, will take same time.
So plzz help me if I m going to the wrong direction..

Title: Re: Mutigraph to Undirected Graph
Post by towr on Nov 18^th, 2007, 9:14am

Hmm, adjacency list is just a list of pairs (v, v')? (I'm not well-versed in graph theory and terminology)
I suppose you could go with a hash-table to attain uniqueness (and weeding out self-loops is trivial enough).