Undirected graph has scanning tree

Reference no: EM13168313

undirected graph has scanning trees. The minimal scanning tree is the scanning tree with the minimal sum of weights on edges. The minimal scanning tree can be found by using Prim's algorithm .

Write a program using C++ to find the minimal scanning tree of a graph. The graph is represented by an adjacency matrix. The adjacency matrix of a graph G = <V, E>

For example, the adjacency matrix of the following graph is on its right side:

The following is Prim's algorithm:

The input of your program should be in the following format:

For example, the input corresponding to the above graph is:

5 1

0 1 3 -1 -1

1 0 3 6 -1

3 3 0 4 2

-1 6 4 0 5

-1 -1 2 5 0

Note that infinity is represented by -1.

The output of your program should be the adjacency matrix of the minimal spanning tree.

For example, the output for the above input is:

0 1 3 -1 -1

1 0 -1 -1 -1

3 -1 0 4 2

-1 -1 4 0 -1

-1 -1 2 -1 0

Reference no: EM13168313

Questions Cloud

Calculate the mass of lead nitrate that had to be added : Sodium nitrate was added to 2.0 L of water at 25 °C to produce a saturated solution. The solution was then heated to 80 °C. Calculate the mass of lead nitrate that had to be added to produce a saturated solution at that higher temperature.

Pragmatically savvy : Below are descriptions of four university professors. Hopefully you will never have an instructor like any of them because they are not very pragmatically savvy.

Draw the logic diagram for a circuit that resolves priority : Q: "Draw the Logic diagram for a circuit that resolves priority among eight active-low inputs, 10_L-17_L, where 10_L has the highest priority.

Describe the australian qualifications framework : Describe the Australian Qualifications Framework. Include a table showing the characteristics of AQF levels and explain the process of developing a training package. List key stakeholders and outline their roles in the process

Undirected graph has scanning tree : undirected graph has scanning trees. The minimal scanning tree is the scanning tree with the minimal sum of weights on edges. The minimal scanning tree can be found by using Prim's algorithm

Sexual response cycle : During the excitement Phase of the sexual response cycle:

Give the contents of eax : in each additional instruction in this problem, assume that EAX contains a given contents before the instruction is executed, and give the contents of EAX as well as the values of the CF, OF, SF, and ZF flags after the instruction is executed:

Construct a 3-bit counter using three d flip-flop : Construct a 3-bit counter using three D flip-flops and a selection of logic gates. The inputs should consist of a signal that resets the counter to 0, called reset

Threatened or actively turned towards communism : Why do you think so many nations chose to pick this time end of warld war II as their own "spring" into greater independence? What were the major grievances they held? And, if they did so, why do you think that so many threatened or actively turned t..

User Account

All Pages