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

Link list, algorithm for multiplication of two sparse matrices using link l... algorithm for multiplication of two sparse matrices using link list

Average case anaysis, what is the impoartance of average case analysis of ... what is the impoartance of average case analysis of algorithm

Inequalities, #question.show that the following inequality is correct or in... #question.show that the following inequality is correct or incorrect. n!=O(n^n)

Ruby implements range of t abstract data type, Ruby implements Range of T A... Ruby implements Range of T Abstract data type Ruby implements Range of T ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

Implementation of dequeue, Dequeue (a double ended queue) is an abstract da... Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Linked list implementation of a queue, The fundamental element of linked li... The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

Explain stacks, What are stacks? A stack is a data structure that organ... What are stacks? A stack is a data structure that organizes data similar to how one organizes a pile of coins. The new coin is always placed on the top and the oldest is on the

Computational complexity, Generally, Computational complexity of algorithms... Generally, Computational complexity of algorithms are referred to through space complexity (space needed for running program) and time complexity (time needed for running the progr

The smallest element of an array''s index, The smallest element of an array... The smallest element of an array's index is called its Lower bound.

Sorted list using binary search technique, Write an algorithm for searching... Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X