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
List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Explain about the Abstract data type Abstract data type (ADT) A set of values (the carrier set) and operations on those values

explain quick sort algorithm

Write an algorithm for compound interest.

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

Example: Assume the following of code: x = 4y + 3 z = z + 1 p = 1 As we have been seen, x, y, z and p are all scalar variables & the running time is constant irrespective