Construct a minimum spanning tree, Data Structure & Algorithms

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







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
Related Questions
algorithm for multiplication of two sparse matrices using link list

what is the impoartance of average case analysis of algorithm

#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 ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

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

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 .

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

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 is called its Lower bound.

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