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

Ask an Expert

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

Write your message here..

Related Questions

Define complete binary tree, Define Complete Binary Tree Complete Binar... 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.

Example of telephone directory, A telephone directory having n = 10 records... 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"

Write a program for linear search, In the book the following methods are pr... In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

Multiple stacks, how multiple stacks can be implemented using one dimension... how multiple stacks can be implemented using one dimensional array

Dataset for dmi, The following DNA sequences are extracted from promoter re... 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

Explain in brief the asymptotic notations, Question 1 Write the different ... 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

Kruskals algorithm, Krushkal's algorithm uses the concept of forest of tree... 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

Designed to manage the booking, Beauty Salon is a system to be designed to... 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

Homework, Write a recursive function the computes the number of digits in a... 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

Advantages of the last in first out method, Materials consumed are priced i... 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