Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connected to A through an edge, remove the directed edge from A to B as well. After this pruning step, we should be left with a graph G' that has only symmetric edges similar to an undirected graph. Now assign each edge a weight randomly picked between [1 W]. 

Then make your program capable of answering the following queries:

1)  Is G' a fully-connected graph? Answer based on a BFS or DFS.

2)  Construct the MST of G'. What is the total weight of G'?

Posted Date: 3/20/2013 2:07:31 AM | Location : United States

Ask an Expert

Related Discussions:- Construct a minimum spanning tree, Assignment Help, Ask Question on Construct a minimum spanning tree, Get Answer, Expert's Help, Construct a minimum spanning tree Discussions

Write discussion on Construct a minimum spanning tree
Your posts are moderated

Write your message here..

Related Questions

Darw a flowchart that inputs country someone is visiting, Regis lives in Br... Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

Sparse matrix, what are the disadvantages of sparse matrix? what are the disadvantages of sparse matrix?

Algorithm for insertion into the circular queue, Algorithm for insertion of... Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Adjacency matrix representation of a graph, An adjacency matrix representat... An adjacency matrix representation of a graph cannot having information of : Parallel edges

Algorithms for push and pop operation, Q. Suggest a method of implementing ... Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

Curve, write a c++ program to find out the area of a curve y=f(x) between x... write a c++ program to find out the area of a curve y=f(x) between x=a and x=b

Darw a flowchart for inputs number of hours of sunshine, This algorithm inp... This algorithm inputs number of hours of sunshine recorded every day for a week (7 days). Output is the highest value for hours of sunshine and average (mean) value for numbers of

Explain the term group support system, (a) Explain the term Group Support S... (a) Explain the term Group Support System and elaborate on how it can improve groupwork. (b) Briefly explain three advantages of simulation. (c) Explain with the help of a

Insertion in list, In the array implementation of lists, elements are store... In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

Pseudo code, I need help writing a pseudocode for my assignment can anyone ... I need help writing a pseudocode for my assignment can anyone help?