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
Explain binary search with an example

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Explain the Interfaces in Ruby Recall that in object-oriented programming, an interface is a collection of abstract operations that cannot be instantiated. Even though Ruby i

Write an algorithm using pseudocode which takes temperatures input over a 100 day period (once per day) and output the number of days when the temperature was below 20C and the num

write a program that find,search&replace a text string

An AVL tree is a binary search tree that has the given properties: The sub-tree of each of the node differs in height through at most one. Each sub tree will be an AVL tre

A striking application of DFS is determine a strongly connected component of a graph. Definition: For graph G = (V, E) , where V refer to the set of vertices and E refer to the

Implement algorithm to solve 5-1 fifth order equation given.

Write an algorithm to count number of nodes in the circular linked list.                            Ans. Counting No of Nodes in Circular List Let list be a circular h

GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EXAMPLE.