Find a minimum spanning tree for each component

Assignment Help Computer Engineering

Reference no: EM132211188

Question :

Write a program to process a weighted undirected graph as follows.

(a) Read in the number of vertices V and the number of edges E of the graph followed by its E edges, each in the form u, v, w where 1 <= u, v <= V & w > 0 representing an edge uv with weight w.

(b) Set up and print the adjacency matrix representation of the Graph.

(d) Find a minimum spanning tree for each component and print the minimum spanning forest in adjacency matrix representation (regardless it has just one or more than one components). You should document your program, analyze the complexity of your algorithms, and show the outputs from sample data sets in the following.

graph one:

19,1,3

1,20,5

1,2,7

2,4,7

4,5,10

17,5,5

18,5,20

8,3,3

7,8,2

16,7,6

7,10,5

4,10,7

6,11,6

11,12,10

9,13,12

7,13,10

13,14,8

10,14,50

14,11,100

15,11,12

6,4,5

1,9,20

8,4,15

17,12,33

15,18,5

graph two

1,9,3

1,2,1.2

2,,5,0.5

2,3,0.8

3,6,3.1

3,10,1.5

4,9,3.2

4,5,1.5

5,7,2

5,8,5.1

10,8,8.8

6,7,5.5

graph three

1,4,2.3

1,9,1.5

1,5,2.4

7,4,8.3

5,4,3.1

9,5,5.6

7,9,0.8

8,6,3.1

8,2,8.2

2,3,1.5

2,10,6.3

3,6,3.2

3,10,5.6

graph four

1,3,1.2

1,2,3.1

2,3,2.5

6,7,0.8

6,9,1.2

6,15,9.8

7,9,0.8

7,15,1.1

7,12,3

12,9,2.5

15,12,3.1

4,5,1.2

4,8,3

5,13,1.6

13,8,6.1

11,8,3.2

11,10,1.2

10,8,5.1

10,14,2.1

13,14,3.1

Reference no: EM132211188

Questions Cloud

Complete client individual tax return for the given year : Jenny Clark is a flight attendant employed by Virgin Australia. She is single and owns an apartment in Sandy Bay, which she purchased in 2003.

Cyber crime and terrorism : How is BLUE OCEAN STRATEGY different from the conventional competitive strategy. Cyber Crime and Terrorism.

Kaizer plastics produces variety of plastic items : Kaizer Plastics produces a variety of plastic items for packaging and distribution.

Description of beauty supply distribution company : Needing a good description of a beauty supply distribution company.

Find a minimum spanning tree for each component : Find a minimum spanning tree for each component and print the minimum spanning forest in adjacency matrix representation.

Characterizes the productivity measurement process : Which of the following statements best characterizes the productivity measurement process?

How well they segment their market : Visit three web services of fast moving consumer goods (FCMG) companies (for example Unilever and P&G). Is there evidence of a segmented approach.

Italian restaurant specializing in venetian cuisine : The three of you ate out last night at a local establishment in Anderson called "Via Egnatia," an Italian restaurant specializing in Venetian cuisine.

How the income should be allocated to the partners : During its first year, the partnership earned $240,000. Prepare calculations showing how the $240,000 income should be allocated to the partners under.

User Account

All Pages