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
Q. Write  down a   programme  in  C  to  create  a  single  linked  list also  write the functions to do the following operations (i)  To insert a new node at the end (ii

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

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.

Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

Memory Allocation Strategies If it is not desirable to move blocks of due storage from one area of memory to another, it must be possible to relocate memory blocks that have be

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

Thus far, we have been considering sorting depend on single keys. However, in real life applications, we may desire to sort the data on several keys. The simplest instance is that

discuss the operating system under the following: MONOLITHIC SYSTEM,LAYER SYSTEM AND VIRTUAL MACHINES