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
In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Ask question 1. Indicate whether each of the following properties is true for every Huffman code. a. The codewords of the two least frequent symbols have the same length. b. The

write pseudocode to implement a queue with two stacks

How sparse matrix stored in the memory of a computer?

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

The simplest implementation of the Dijkstra's algorithm stores vertices of set Q into an ordinary linked list or array, and operation Extract-Min(Q) is just a linear search through

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 .

I need to know about data structure and algorithms. can you help me?

An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found. The cause for sorting an array is that we search

The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o