P7. Ch 29 - Weighted Graphs Q.1 (Exer 29.9) Find a minimum spanning tree. Write a program that reads a connected graph from a file and displays its minimum spanning tree. The first line in the file contains a number that indicates the number of vertices (n). The vertices are labeled as 0, 1, ..., n-1. Each subsequent line describes the edges in the form of u1, v1, w1 I u2, v2, w2 I.... Each triplet in this form describes an edge and its weight. Figure 29.24 shows an example of the file for the corresponding graph. Note that we assume the graph is undirected. OMN N 0 3 2 2 4 100 40 5 9 1 8 m 20 3 5 5 File 6 0, 1, 100 | 0, 2, 3 1, 3, 20 2. 3. 40 | 2, 4, 2 3, 4, 53, 5, 5 4, 5, 9 (b) FIGURE 29.24 The vertices and edges of a weighted graph can be stored in a file. If the graph has an edge (u, v), it also has an edge (v. u). Only one edge is represented in the file. When you construct a graph, both edges need to be added. Your program should prompt the user to enter the name of the file, read data from the file, create an instance g of WeightedGraph, invoke g.printWeighted Edges() to display all edges, invoke getMinimumSpanning Tree() to obtain an instance tree of WeightedGraph.MST, invoke tree.getTotalWeight() to display the weight of the minimum spanning tree, and invoke tree.printTree() to display the tree. Here is a sample run of the program: Enter a file name: c:\exercise\WeightedGraphSample.txt The number of vertices is 6 Vertex 0: (0, 2, 3) (0, 1, 100) Vertex 1: (1, 3, 20) (1, 0, 100); Vertex 2: (2, 1, 2) (2, 3, 10) (2, 0, 3) Vertex 3: (3. 4. 5) Vertex 4: (4, 2, 2) Vertex S: (5. 3. 5) (5. 4. 9) (3. 5. 5) (5. 1. 20) (3. 2. 40) (4, 3, 5) (4, 5, 9) Total weight in MST is 35 Root is: 0 Edges: (3, 1) (0, 2) (4, 3) (2, 4) (3, 5)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

PLEASE type IN JAVA. IF YOU HAVE ANY EXTRA QUESTIONS OR FEEL SOMETHING IS MISSING PLEASE DONT CANCEL THE QUESTION. If theres a way to contact me or comment please do that instead of canceling the whole question. Below are the attached files . Please type code so I can copy and paste it in my IDE. Also add comments. (they dont have to be too long, just keep it simple.) Be sure to screenshot your output so I can see and make sure it printed out the right thing.

(Hint: Use new WeightedGraph(list, numberOfVertices) to create a graph, where list contains a list of
Weighted Edge objects. Use new WeightedEdge(u, v, w) to create an edge. Read the first line to get the
number of vertices. Read each subsequent line into a string s and use s.split("[V]") to extract the triplets.
For each triplet, use triplet.split("[.]") to extract vertices and weight.)

P7. Ch 29 - Weighted Graphs
Q.1 (Exer 29.9) Find a minimum spanning tree. Write a program that reads a connected graph from a file
and displays its minimum spanning tree. The first line in the file contains a number that indicates the
number of vertices (n).
The vertices are labeled as 0, 1,..., n-1. Each subsequent line describes the edges in the form
of u1, v1, w1 I u2, v2, w2 I.... Each triplet in this form describes an edge and its weight. Figure 29.24
shows an example of the file for the corresponding graph. Note that we assume the graph is undirected.
0
3
2
2
100
40
5
9
20
3
5
File
6
0, 1, 100 | 0, 2, 3
1, 3, 201
2. 3. 40
2, 4, 2
3, 4, 53, 5, 5
4, 5, 9
(a)
(b)
FIGURE 29.24 The vertices and edges of a weighted graph can be stored in a file.
If the graph has an edge (u, v), it also has an edge (v. u). Only one edge is represented in the file. When
you construct a graph, both edges need to be added.
Your program should prompt the user to enter the name of the file, read data from the file, create an
instance g of WeightedGraph, invoke g.printWeighted Edges() to display all edges, invoke
getMinimumSpanning Tree() to obtain an instance tree of WeightedGraph.MST, invoke
tree.getTotalWeight() to display the weight of the minimum spanning tree, and invoke tree.printTree() to
display the tree.
Here is a sample run of the program:
Enter a file name: c:\exercise\WeightedGraphSample.txt
The number of vertices is 6
Vertex 0: (0, 2, 3) (0, 1, 100)
Vertex 1: (1, 3, 20) (1, 0, 100)
Vertex 2: (2, 1, 2) (2, 3, 10) (2, 0, 3)
Vertex 3:
Vertex 4: (4, 2, 2)
Vertex 5: (5. 3. 5) (5. 4, 9)
Total weight in MST is 35
Root is: 0
Edges: (3, 1) (0, 2) (4, 3) (2, 4) (3, 5)
(3. 4. 5) (5. 5. 5) (5. 1. 20) (3. 2. 40)
(4, 3, 5) (4, 5, 9)

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions