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