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
Searching is the procedure of looking for something. Searching a list containing 100000 elements is not the similar as searching a list containing 10 elements. We discussed two sea

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.

In a circular linked list There is no beginning and no end.

What do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func

If a node having two children is deleted from a binary tree, it is replaced by?? Inorder successor

Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write fu

Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

One of the main problems with the linear queue is the lack of appropriate utilization of space. Assume that the queue can store 100 elements & the complete queue is full. Thus, it

Multidimensional array: Multidimensional arrays can be defined as "arrays of arrays". For example, a bidimensional array can be imagined as a bidimensional table made of elements,

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram wh