Question: Attached to this assignment is a text file called graphdata.txt. Each line represents one edge in a graph; the first two numbers are the vertices
Attached to this assignment is a text file called graphdata.txt. Each line represents one edge in a graph; the first two numbers are the vertices and the third number is the weight. You are to write a Java program to read in the graph data, create an EdgeWeightedGraph object from it, and then use two different algorithms to find the minimum spanning tree for this graph data.
This data represents an undirected graph.
There are exactly 100 vertices in this graph.
You should use the appropriate classes from the authors web site (algs4.cs.princeton.edu) for this assignment. As an example, download and use his EdgeWeightedGraph.java.
Use both Kruskals and Prims algorithm.
Compare the results, in terms of number of edges, total weight and time. I want to see an output line something like Prims algorithm found an MST of 171 edges, with a total weight of 3055, in 0.000038 seconds.
Finally, discuss your findings.
Your report will consist of:
1. Your Java source code for the final program (just your class, not any of the authors);
2. The output from your program;
graphdata.txt file:
1 7 96
1 11 96
1 21 50
1 79 49
1 99 50
2 4 51
2 7 14
2 53 40
2 91 49
3 26 35
3 57 22
3 72 1
4 22 89
4 33 78
5 11 86
5 19 60
5 42 63
5 79 6
5 91 62
6 8 63
6 66 35
6 90 79
7 8 3
7 44 16
7 51 28
7 60 69
7 74 84
7 77 3
7 93 98
8 12 40
8 69 74
8 73 30
8 77 19
8 89 52
8 92 39
9 20 69
9 28 39
9 39 41
9 41 95
9 44 29
9 50 8
9 74 1
9 84 14
9 88 81
10 43 53
10 47 14
10 73 79
10 98 2
11 51 73
11 67 70
11 68 52
11 99 11
12 86 64
13 43 70
13 56 20
13 95 25
14 23 90
14 26 29
14 58 90
14 65 94
14 78 61
14 92 84
15 30 14
15 47 99
15 56 28
15 57 48
15 59 11
15 82 6
16 25 59
16 47 37
16 50 26
16 67 17
16 81 92
17 25 55
17 27 84
17 43 13
17 45 40
17 58 15
17 61 75
18 32 62
18 37 11
18 51 83
19 24 9
19 50 71
19 55 77
19 65 18
20 31 62
20 33 13
20 84 33
21 39 59
21 66 87
22 41 7
22 90 24
23 39 99
23 41 3
23 52 20
23 56 21
24 25 91
24 51 90
24 65 2
24 75 68
25 49 72
25 52 42
25 87 5
26 27 43
26 56 87
26 57 99
26 88 31
26 90 80
27 32 3
27 46 98
27 59 47
27 61 35
27 64 84
27 75 78
27 79 97
27 85 17
27 89 94
27 100 80
28 78 53
28 80 55
28 94 25
28 96 70
29 35 84
29 40 95
29 68 64
29 72 10
29 92 82
30 36 95
30 37 26
30 55 59
30 69 76
30 90 12
31 78 86
31 86 71
32 43 26
32 50 59
32 63 46
32 64 20
32 76 28
32 85 64
32 89 79
33 76 79
33 80 74
33 88 15
34 71 6
34 77 55
34 89 51
35 39 34
35 75 96
35 76 61
35 99 85
36 46 47
36 49 60
36 86 8
37 67 90
37 69 47
37 100 15
38 57 27
38 70 95
39 57 88
40 63 30
40 86 34
40 92 51
41 60 34
42 48 18
42 57 80
42 81 63
42 90 67
42 91 36
42 93 53
43 47 80
43 77 7
43 80 4
43 95 91
45 61 81
45 64 29
46 66 4
46 69 56
46 100 91
47 62 57
47 88 52
48 55 2
49 53 37
49 56 29
49 68 38
49 98 26
50 66 27
50 72 85
50 80 52
51 54 57
51 61 42
51 62 32
51 72 48
51 76 33
51 83 70
52 85 47
52 94 33
53 64 50
53 79 19
54 63 79
54 79 50
55 74 15
55 82 48
55 84 35
56 60 64
56 89 64
57 80 71
58 93 94
58 94 10
58 96 68
59 66 62
59 67 45
60 62 58
60 78 42
60 90 61
60 99 31
61 80 98
61 93 41
61 99 28
63 94 79
63 98 16
63 100 73
64 76 83
66 67 77
66 70 23
66 72 49
66 88 4
67 78 21
67 95 3
68 72 31
69 94 31
70 71 22
70 79 54
71 80 47
71 82 34
71 94 63
73 74 89
73 77 17
73 78 70
73 84 69
73 85 43
76 84 15
77 96 80
79 80 34
80 81 54
80 83 39
80 100 98
81 100 89
82 86 99
82 92 88
82 95 59
83 86 79
84 95 17
84 100 82
86 90 73
86 100 74
87 92 74
87 94 21
87 96 9
88 97 17
89 90 22
89 97 82
91 93 100
91 94 54
93 94 40
93 95 73
95 96 99
95 99 56
96 99 23
97 99 66
99 100 69
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help