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
Representation of Linked list in Memory:- Each node has an info part and a pointer to the next node also known as link. The number of pointers is two in case of doubly linked

Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?

What data structure would you mostly likely see in a nonrecursive execution of a recursive algorithm? Stack

Write a function that performs the integer mod function. Given the previous functions you have implemented already, this one should be a piece of cake. This function will find the

how to reduce the number of passes in selection sort


how to define the size of array

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

B- Tree  A B-tree of order m is an m-way true in which  1)  All leaves are on the similar level 2)  All internal nodes except the root have at most m-1(non-empty) childre

Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a