Author |
Topic: Mutigraph to Undirected Graph (Read 1113 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
Mutigraph to Undirected Graph
« on: Nov 18th, 2007, 3:25am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Mutigraph to Undirected Graph
« Reply #1 on: Nov 18th, 2007, 7:02am » |
Quote Modify
|
Initialize the adjacency matrix to empty; then fill in all the edges, except those on the diagonal.
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Mutigraph to Undirected Graph
« Reply #2 on: Nov 18th, 2007, 8:25am » |
Quote Modify
|
but we have to find adjacency list, and if we use adjacency matrix then our algorithm will take O(|V|2) 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..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Mutigraph to Undirected Graph
« Reply #3 on: Nov 18th, 2007, 9:14am » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print