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
Define Complete Binary Tree Complete Binary Tree:- A whole binary tree of depth d is that strictly binary tree all of whose leaves are at level D.

A telephone directory having n = 10 records and Name field as key. Let us assume that the names are stored in array 'm' i.e. m(0) to m(9) and the search has to be made for name "X"

In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

how multiple stacks can be implemented using one dimensional array

The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

Question 1 Write the different characteristics of an algorithm Question 2 Explain in brief the asymptotic notations Question 3 Write an algorithm of insertion sort and e

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

Beauty Salon is a system to be designed to manage the booking and the payment of a single beauty parlour. Beauty Therapists: A beauty parlour has a number of staff members mo

Write a recursive function the computes the number of digits in a positive integer n. For example if n = 6598, the function should return 4. Find a variant expression and a thresho

Materials consumed are priced in a systematic and realistic manner. It is argued that current acquisition costs are incurred for the purpose of meeting current production and sales