1
00:00:00,900 --> 00:00:03,150
Hi, everyone, welcome to this new video.

2
00:00:03,180 --> 00:00:07,080
So in this video, we are going to discuss the algorithm for Kruskal.

3
00:00:07,650 --> 00:00:11,960
So this is basically for finding out the minimum spending rate.

4
00:00:12,150 --> 00:00:15,390
The algorithm is basically greedy algorithm.

5
00:00:16,440 --> 00:00:19,920
So algorithm basically involved just two step.

6
00:00:20,310 --> 00:00:23,970
So first step algorithm is basically what you will do.

7
00:00:23,970 --> 00:00:25,230
You will start the edges.

8
00:00:27,590 --> 00:00:34,040
We will sort the edges in increasing order of rates, so, for example, here are rates nine, then

9
00:00:34,040 --> 00:00:35,070
five, then 10.

10
00:00:35,360 --> 00:00:41,950
So we are going to sort the edges on basis of which second is basically what they will do.

11
00:00:42,710 --> 00:00:44,240
You will pick the edge.

12
00:00:44,240 --> 00:00:47,170
You will pick these sorted edges one by one.

13
00:00:47,840 --> 00:00:55,310
So we are going to pick these sorted edges one by one, and we will add them in the minimum spending

14
00:00:55,310 --> 00:00:55,620
three.

15
00:00:55,640 --> 00:00:59,720
But the condition is edge should not make a single big.

16
00:00:59,720 --> 00:01:02,990
These is only if it is safe.

17
00:01:03,590 --> 00:01:08,660
So what do I mean by a safe safe means cycle should not be there.

18
00:01:09,320 --> 00:01:14,840
Pecl not pleasant by picking the edge.

19
00:01:14,840 --> 00:01:17,980
They should not be cycle in the spending tree.

20
00:01:19,290 --> 00:01:19,550
Right.

21
00:01:20,090 --> 00:01:21,500
Let me write it clearly.

22
00:01:22,610 --> 00:01:23,720
These are teenagers.

23
00:01:27,100 --> 00:01:27,730
And.

24
00:01:30,710 --> 00:01:33,020
Edge should not make cycling.

25
00:01:34,280 --> 00:01:37,510
This is better and should not make a second.

26
00:01:39,380 --> 00:01:43,830
So these two other steps of critical algorithm, very, very simple algorithm.

27
00:01:44,120 --> 00:01:47,280
So let me run these steps on this example.

28
00:01:47,450 --> 00:01:48,680
So this is a graph, right?

29
00:01:49,010 --> 00:01:51,170
This is a graph given to us.

30
00:01:51,180 --> 00:01:55,820
We need to find out the minimum spending tree and let's use algorithm.

31
00:01:55,850 --> 00:01:58,700
So what this is, it is sort of the edges.

32
00:01:58,730 --> 00:02:01,460
OK, so let's say I have sorted edges.

33
00:02:01,700 --> 00:02:04,270
I have sorted all the edges based on their weight.

34
00:02:04,610 --> 00:02:08,060
Now, what we need to do, we need to pick these sorted edges one by one.

35
00:02:08,360 --> 00:02:09,770
So what is the minimum wage here?

36
00:02:10,250 --> 00:02:13,180
So this is 11, five, 10 minimum wage.

37
00:02:13,190 --> 00:02:14,070
Is this one right?

38
00:02:14,570 --> 00:02:15,710
This is the minimum wage.

39
00:02:16,840 --> 00:02:20,560
This is the minimum wage, so I will pick this age, let's pick this age.

40
00:02:24,200 --> 00:02:34,280
So I am picking this edge in our spending tree, so this is my minimum spending tree, so in my spending

41
00:02:34,280 --> 00:02:37,300
tree I have decided that there will be an edge.

42
00:02:38,060 --> 00:02:42,890
I have selected for stage, for entry and the way this tree.

43
00:02:43,370 --> 00:02:43,790
Right.

44
00:02:44,240 --> 00:02:46,420
So we have the edge.

45
00:02:46,430 --> 00:02:48,570
And currently there is no cycle, right.

46
00:02:48,590 --> 00:02:49,330
There is no cycle.

47
00:02:49,340 --> 00:02:50,870
This is about amnesty for entry.

48
00:02:51,170 --> 00:02:52,190
No cycle is there.

49
00:02:52,400 --> 00:02:53,960
Or what can I do.

50
00:02:56,690 --> 00:03:05,430
For better understanding, let me write for entry here four and three, so I have picked this edge.

51
00:03:05,810 --> 00:03:07,570
Now let's pick the second.

52
00:03:07,790 --> 00:03:10,620
You can see this is not making any second, right.

53
00:03:10,690 --> 00:03:11,940
There is no cycling domestic.

54
00:03:12,290 --> 00:03:14,360
Now, let's pick the second minimum wage.

55
00:03:14,840 --> 00:03:18,020
So after three, this is six, seven, ten.

56
00:03:18,020 --> 00:03:22,490
I think five rate five is the minimum wage right now.

57
00:03:22,730 --> 00:03:24,200
So let's pick this age.

58
00:03:26,370 --> 00:03:32,340
Let's pick this age, which is zero and two, so I am picking the age zero.

59
00:03:33,930 --> 00:03:39,040
To to hear the story and hear the it is five.

60
00:03:39,310 --> 00:03:42,700
OK, so currently this is our amnesty and amnesty.

61
00:03:42,720 --> 00:03:45,140
There is no cycle right now.

62
00:03:45,150 --> 00:03:46,650
Let's pick the third age.

63
00:03:47,700 --> 00:03:51,960
We are picking the age in this hour, 30 minutes or the third age after three and five.

64
00:03:52,590 --> 00:03:54,710
I think it is six, right?

65
00:03:54,720 --> 00:03:55,740
It is six years.

66
00:03:56,340 --> 00:03:57,750
So let's pick this age.

67
00:04:00,860 --> 00:04:11,080
Let's pick this age, so if I pick the edge, if I pick this age the way it is six and there is no cycle,

68
00:04:11,090 --> 00:04:14,210
so currently there is no cycle present in our midst.

69
00:04:14,210 --> 00:04:18,300
So I can pick this age now let's pick the next age.

70
00:04:18,320 --> 00:04:20,029
So after six, I think seven.

71
00:04:20,450 --> 00:04:22,180
So let's try to pick this age.

72
00:04:22,340 --> 00:04:27,500
So if you will pick this age right, if you will pick this age, then there will be a cycle.

73
00:04:27,860 --> 00:04:29,420
A cycle will be formed.

74
00:04:29,900 --> 00:04:35,270
If you pick this age seven, that means you cannot pick this age.

75
00:04:35,270 --> 00:04:35,570
Right.

76
00:04:35,580 --> 00:04:40,160
What is the condition after picking the age check whether there is a cycle or not.

77
00:04:40,370 --> 00:04:46,280
If you will pick this age seven, then a cycle will be formed in the middle of spanning spending.

78
00:04:46,280 --> 00:04:51,620
Three and we do not want cycle spanning three are basically acyclic.

79
00:04:51,620 --> 00:04:53,420
So we cannot pick this age.

80
00:04:53,810 --> 00:04:55,040
I cannot pick this age.

81
00:04:55,040 --> 00:04:57,750
So let's move on to the next edge that I can pick.

82
00:04:58,130 --> 00:05:02,600
So after seven I can pick ten made.

83
00:05:02,600 --> 00:05:04,850
Ten is minimum so I can pick ten.

84
00:05:05,090 --> 00:05:10,100
So after picking ten, yes I can pick ten because they will be no cycle.

85
00:05:10,460 --> 00:05:21,680
So I can pick ten because there is no cycle introduced because of picking this age right now after ten

86
00:05:22,130 --> 00:05:25,180
which edge I can pick so.

87
00:05:25,980 --> 00:05:26,990
Sorry, sorry, sorry.

88
00:05:26,990 --> 00:05:28,170
This is, this was nine.

89
00:05:29,810 --> 00:05:30,700
Please forgive me.

90
00:05:30,710 --> 00:05:33,320
Actually this was nine so we need to pick nine first.

91
00:05:34,970 --> 00:05:39,440
We will not, we will not pick this will first pick nine.

92
00:05:39,740 --> 00:05:42,680
After seven after seven we will pick nine.

93
00:05:43,130 --> 00:05:44,000
Nine is minimum.

94
00:05:44,000 --> 00:05:45,050
So let's pick nine.

95
00:05:46,430 --> 00:05:51,350
So after picking nine there is no second introduced so we can pick nine.

96
00:05:51,350 --> 00:05:52,220
Nine is safe.

97
00:05:52,220 --> 00:05:52,640
Twelve.

98
00:05:54,120 --> 00:06:02,750
This is nine now after nine, which is gigantic, so this is 10, 11 and 12, so three are remaining.

99
00:06:02,970 --> 00:06:08,490
If I pick this age 10, if I pick this age 10, then what will happen?

100
00:06:08,820 --> 00:06:12,840
They will be cycle introduced in your spending.

101
00:06:12,840 --> 00:06:14,360
Three, and we do not want a cycle.

102
00:06:14,370 --> 00:06:15,860
That means I cannot pick 10.

103
00:06:16,680 --> 00:06:18,890
So after 10, let's talk about 11.

104
00:06:19,260 --> 00:06:24,510
So if I pick this age, then there will be a cycle introduced so I cannot pick 11.

105
00:06:24,930 --> 00:06:27,260
So let's move on to 12.

106
00:06:28,050 --> 00:06:34,860
So if I pick this age 12, if I pick this age 12, then what will happen today will be the cycle introduced

107
00:06:34,860 --> 00:06:39,720
zero to one one, two, three, three to four, four, two, two and two to zero.

108
00:06:40,170 --> 00:06:40,560
Right.

109
00:06:40,590 --> 00:06:47,240
So in this way, zero two one one, two, three three to four four two two and two two zero.

110
00:06:47,460 --> 00:06:49,620
So they will be a cycle introduced.

111
00:06:49,620 --> 00:06:51,180
So I cannot pick one.

112
00:06:51,690 --> 00:06:54,360
And that's all we have picked all the ages.

113
00:06:54,360 --> 00:06:56,580
And this is our minimum spending tree.

114
00:06:57,330 --> 00:06:59,490
This is our minimum spending spree.

115
00:07:00,660 --> 00:07:04,880
And in this spending spree, so there are how many roads present?

116
00:07:04,890 --> 00:07:07,410
One, two, three, four, five, five nodes at present.

117
00:07:07,800 --> 00:07:12,590
So how many items should be there and spending three, four edges should be there in spending three.

118
00:07:12,720 --> 00:07:15,000
And we can see there are four Reges rate.

119
00:07:15,120 --> 00:07:17,250
So this is your minimum spending three.

120
00:07:19,660 --> 00:07:20,120
Right.

121
00:07:20,530 --> 00:07:27,790
So I have highlighted here also we have picked this age, we have picked this age, we have picked this

122
00:07:27,790 --> 00:07:29,890
age and we have picked this age.

123
00:07:30,880 --> 00:07:32,890
So this is our medium spanning three.

124
00:07:34,000 --> 00:07:34,380
Right.

125
00:07:35,470 --> 00:07:37,870
So that's how Kruskal algorithm works.

126
00:07:38,890 --> 00:07:40,220
What is the total cost?

127
00:07:40,240 --> 00:07:44,860
This is nine plus nine plus five plus six plus three.

128
00:07:44,860 --> 00:07:47,650
Nine plus five plus six plus three.

129
00:07:47,950 --> 00:07:49,490
That is 23.

130
00:07:49,510 --> 00:07:51,490
So 23 is the minimum cost.

131
00:07:52,620 --> 00:07:54,890
Right now, let's take one more example.

132
00:07:57,030 --> 00:07:59,400
Let's talk about this example.

133
00:08:03,020 --> 00:08:06,350
So what do we need to pick the ideas in SA today?

134
00:08:07,520 --> 00:08:09,290
So what is the minimum age?

135
00:08:09,860 --> 00:08:14,300
So I think this is the minimum age.

136
00:08:14,300 --> 00:08:15,630
Is this one one?

137
00:08:16,490 --> 00:08:18,770
This is the minimum wage.

138
00:08:19,520 --> 00:08:21,290
So let's pick this age.

139
00:08:22,460 --> 00:08:29,570
So after picking this age, there is no cycle so we can pick this age now after one, which is just

140
00:08:29,570 --> 00:08:30,110
the minimum.

141
00:08:30,380 --> 00:08:39,470
So I think we have to here and we have to here also so we can pick any one of them.

142
00:08:39,470 --> 00:08:42,360
I can pick this or I can pick this rate.

143
00:08:42,380 --> 00:08:43,280
They both are equal.

144
00:08:43,549 --> 00:08:45,110
So you can pick any of them.

145
00:08:45,110 --> 00:08:46,820
Let's say I am picking this one.

146
00:08:47,760 --> 00:08:51,570
Since they both are equal, so you can pick any one of them, so if I am picking this.

147
00:08:53,780 --> 00:08:59,090
So after picking this age, there is no cycle introduced in the graph, there is no cycle in reducing

148
00:08:59,090 --> 00:08:59,460
the tree.

149
00:08:59,480 --> 00:09:01,890
So you can pick this age now after two.

150
00:09:02,150 --> 00:09:03,330
I need to pick this.

151
00:09:04,130 --> 00:09:07,410
So if I pick this, can I pick this?

152
00:09:07,430 --> 00:09:07,700
Yes.

153
00:09:07,700 --> 00:09:09,080
There is no single introduced.

154
00:09:09,080 --> 00:09:13,130
So you can pick this age now after two, which is the minimum age.

155
00:09:14,510 --> 00:09:18,630
So food and we have food here also.

156
00:09:18,650 --> 00:09:22,080
So again, you can pick any one of them in any order.

157
00:09:22,340 --> 00:09:28,720
So if I pick this age so after picking this age, is there any cycle.

158
00:09:29,900 --> 00:09:31,170
So can I pick this age?

159
00:09:31,190 --> 00:09:32,830
Yes, I can pick this age.

160
00:09:32,840 --> 00:09:34,190
There is no cycle introduced.

161
00:09:34,430 --> 00:09:36,320
So this is yes.

162
00:09:36,320 --> 00:09:37,550
There is no cycle introduced.

163
00:09:37,550 --> 00:09:39,380
So I can pick this age four.

164
00:09:39,890 --> 00:09:44,060
So after picking food, this is the next smallest rate.

165
00:09:44,270 --> 00:09:45,770
So let's pick this age.

166
00:09:46,100 --> 00:09:51,530
So after picking this age again, there is no cycle introduced so you can pick this age.

167
00:09:52,580 --> 00:09:57,050
So after four which edge I can pick to eight 11 seven.

168
00:09:57,050 --> 00:09:58,570
What is the minimum after four.

169
00:09:59,240 --> 00:10:02,560
I think it is seven seven.

170
00:10:03,320 --> 00:10:03,760
Yes.

171
00:10:04,070 --> 00:10:10,240
So I have seven here and sorry we have six right after four we need to pick six.

172
00:10:11,150 --> 00:10:16,910
So if I pick this age, if I pick this age, then what will happen.

173
00:10:17,180 --> 00:10:19,100
There will be cycle introduced.

174
00:10:20,400 --> 00:10:26,670
There will be a cycle introduced in the spending tree, so I cannot pick this age, so I cannot pick

175
00:10:26,670 --> 00:10:29,390
this age between eight and six with the weight six.

176
00:10:29,880 --> 00:10:32,570
So after six, what is the next smallest rate?

177
00:10:32,580 --> 00:10:37,700
It is seven and seven is present here as well as seven is present here.

178
00:10:38,070 --> 00:10:40,530
So can I pick this age?

179
00:10:41,970 --> 00:10:46,070
Yes, I think I can pick this age because there will be no cycle introduced.

180
00:10:46,170 --> 00:10:46,920
No, no, no, no.

181
00:10:47,280 --> 00:10:50,340
They will be cycle introduced because it will pick this age.

182
00:10:50,340 --> 00:10:57,770
Then they will cycle like this from here, then this, then this, then this and then basically this.

183
00:10:57,780 --> 00:11:00,240
So you cannot pick this age, right.

184
00:11:00,570 --> 00:11:05,250
You cannot pick this age because this will introduce cycle in your spending tree.

185
00:11:05,910 --> 00:11:07,840
So you cannot pick this age.

186
00:11:07,860 --> 00:11:10,080
Now let's talk about this age, the seven.

187
00:11:10,680 --> 00:11:12,820
So can I pick this age?

188
00:11:12,840 --> 00:11:14,220
Yes, I can pick this age.

189
00:11:14,220 --> 00:11:15,900
There will be no cycle introduced.

190
00:11:16,500 --> 00:11:18,390
So I can pick this age.

191
00:11:18,660 --> 00:11:19,110
Find.

192
00:11:20,170 --> 00:11:27,900
OK, so after 7:00, the next is basically eight, so it is present here as well as here.

193
00:11:28,480 --> 00:11:30,580
So let's first talk about this.

194
00:11:31,000 --> 00:11:32,680
So can I pick this edge?

195
00:11:33,200 --> 00:11:35,410
So if I pick this, will there be any cycle?

196
00:11:36,200 --> 00:11:38,860
Oh, no, I don't think there will be any cycle.

197
00:11:38,860 --> 00:11:40,240
So I can pick this.

198
00:11:42,430 --> 00:11:45,250
There is no second introduced, so I can pick this age.

199
00:11:47,260 --> 00:11:53,530
OK, after it, I have this it so if I pick this age, will there be a cycle?

200
00:11:54,280 --> 00:11:58,240
So let's see whether there will be a cycle or not.

201
00:11:59,080 --> 00:11:59,560
Yes.

202
00:11:59,830 --> 00:12:02,650
If you will pick this age, they will be a cycle introduced.

203
00:12:02,860 --> 00:12:03,310
How?

204
00:12:03,760 --> 00:12:07,630
Because you can see 021 then this.

205
00:12:08,080 --> 00:12:09,430
Then basically this one.

206
00:12:10,270 --> 00:12:11,200
Then this one.

207
00:12:11,860 --> 00:12:12,730
Then this one.

208
00:12:13,000 --> 00:12:14,110
And then this one.

209
00:12:14,440 --> 00:12:17,560
So if you will pick this age, they will be introduced.

210
00:12:17,950 --> 00:12:20,200
So you cannot pick this age.

211
00:12:21,130 --> 00:12:22,890
We cannot pick the edge it.

212
00:12:24,010 --> 00:12:25,760
Now, let's move on to the next one.

213
00:12:26,350 --> 00:12:29,290
So after eight, I think I have nine.

214
00:12:29,530 --> 00:12:29,950
Right.

215
00:12:30,280 --> 00:12:31,220
We have nine here.

216
00:12:31,780 --> 00:12:33,640
So can I pick this age?

217
00:12:34,210 --> 00:12:36,100
Yes, I think I can pick this age.

218
00:12:36,130 --> 00:12:37,780
There will be no cycle introduced.

219
00:12:38,380 --> 00:12:40,180
So let's pick this age.

220
00:12:44,100 --> 00:12:47,800
So after nine, the minimum is, I think, 10.

221
00:12:48,390 --> 00:12:49,500
So can I pick 10?

222
00:12:49,830 --> 00:12:53,580
So if you will pick this age, they will be introduced.

223
00:12:53,730 --> 00:12:59,160
How you can see this, then this, then this and then this.

224
00:12:59,670 --> 00:13:01,260
So you cannot pick 10.

225
00:13:02,130 --> 00:13:05,560
We cannot pick this edge this week.

226
00:13:05,580 --> 00:13:09,720
Then after 10, I think the minimum is 11.

227
00:13:09,960 --> 00:13:10,320
So we.

228
00:13:10,320 --> 00:13:11,790
Can you pick this age?

229
00:13:11,820 --> 00:13:14,160
No, they will be cycle introduced like this.

230
00:13:14,550 --> 00:13:16,040
So you cannot pick 11.

231
00:13:16,410 --> 00:13:20,430
So after 11, the last remaining Verity's 14.

232
00:13:20,430 --> 00:13:21,380
Can you pick 14?

233
00:13:21,390 --> 00:13:25,590
No, you cannot pick 14 because in that case you will have a cycle like this.

234
00:13:26,160 --> 00:13:29,790
And we are done and we are done.

235
00:13:29,790 --> 00:13:33,170
So how our minimum spending will look like.

236
00:13:33,480 --> 00:13:36,300
So this is zero after zero.

237
00:13:36,330 --> 00:13:41,940
I have one here, I have seven here for seven.

238
00:13:41,940 --> 00:13:43,200
I have six here.

239
00:13:43,950 --> 00:13:45,660
Then I have five here.

240
00:13:46,950 --> 00:13:59,420
So here I have two, then I have three, then I have four and then I have eight.

241
00:14:00,000 --> 00:14:15,240
So this is our minimum spanning three and these are weights four eight one two four, seven, nine and

242
00:14:15,240 --> 00:14:15,540
two.

243
00:14:16,710 --> 00:14:21,120
So this is our minimum spending three and these are all node's.

244
00:14:25,610 --> 00:14:32,090
For finding out the cost, for finding out the minimum cost of what you will do, you will add all the

245
00:14:32,090 --> 00:14:39,290
values, you will add four eight one two four, seven, nine and two, and that will be your minimum

246
00:14:39,290 --> 00:14:39,750
cost.

247
00:14:39,950 --> 00:14:41,690
So this is a spending tree.

248
00:14:42,140 --> 00:14:43,450
How many nodes are present?

249
00:14:43,800 --> 00:14:48,870
So one, two, three, four, five, six, seven, eight, nine, nine nodes out there.

250
00:14:49,340 --> 00:14:50,770
So how many ideas should be there?

251
00:14:50,780 --> 00:14:52,760
Eight edges should be there.

252
00:14:52,760 --> 00:14:55,770
So let's count whether it is at present or not.

253
00:14:56,300 --> 00:15:02,720
So one, two, three, four, five, six, seven and eight.

254
00:15:02,990 --> 00:15:06,800
So eight edges are there, nine nodes out there.

255
00:15:07,370 --> 00:15:10,150
And the three is basically connected.

256
00:15:10,160 --> 00:15:14,120
You can see this is connected and there is no cycle.

257
00:15:15,980 --> 00:15:16,450
Right.

258
00:15:16,700 --> 00:15:19,550
So that's how you can use an algorithm.

259
00:15:20,210 --> 00:15:24,740
So you can see the algorithm is very, very simple to do.

260
00:15:24,740 --> 00:15:28,470
You need to sort the edges and you need to pick the edges in sort that way.

261
00:15:28,490 --> 00:15:32,390
And after picking the edge, check whether there is a cycle or not.

262
00:15:32,390 --> 00:15:34,070
If there is a cycle, do not pick.

263
00:15:34,430 --> 00:15:36,080
If no cycle, then pick.

264
00:15:36,500 --> 00:15:36,920
Right.

265
00:15:39,380 --> 00:15:42,870
Now, let's talk about the third example.

266
00:15:43,040 --> 00:15:47,060
So now let's apply them on this example, on this graph.

267
00:15:47,240 --> 00:15:48,440
So, again, very simple.

268
00:15:48,890 --> 00:15:49,970
Pick the minimum wage.

269
00:15:50,180 --> 00:15:53,300
This is the minimum wage and this is safe.

270
00:15:53,300 --> 00:15:56,090
Say there is no cycle introduced after picking this age.

271
00:15:56,720 --> 00:15:58,070
So let's pick this age.

272
00:16:02,480 --> 00:16:08,270
Now, after one month is the minimum wage, so I have to here, I have to here so you can pick in any

273
00:16:08,270 --> 00:16:08,570
order.

274
00:16:08,810 --> 00:16:11,660
Let's see if I pick this so I can pick this.

275
00:16:11,660 --> 00:16:12,620
There will be no cycle.

276
00:16:12,620 --> 00:16:15,790
So let's pick this now after two, the first two.

277
00:16:16,190 --> 00:16:21,770
So let's pick this because there is no cycle after taking after picking this age.

278
00:16:22,130 --> 00:16:25,430
So after two days, the minimum wage to is the minimum wage.

279
00:16:26,000 --> 00:16:32,420
So we can pick this because there is no cycle introduced after picking this age to decide just save.

280
00:16:34,180 --> 00:16:37,010
So after three, I have five.

281
00:16:37,540 --> 00:16:38,830
So can I pick five?

282
00:16:39,550 --> 00:16:44,200
Yes, I can pick five because there is there will be no cycle introduced.

283
00:16:44,200 --> 00:16:45,310
So let's pick five.

284
00:16:46,790 --> 00:16:52,370
After five, the minimum is seven, can I pick seven, you cannot pick seven because in that case they

285
00:16:52,370 --> 00:16:57,410
will recycle introduced so you cannot pick seven now after seven.

286
00:16:57,410 --> 00:17:02,200
I have it here and I have it here so you can pick in any order.

287
00:17:03,140 --> 00:17:05,240
So let's see if I pick this edge.

288
00:17:06,220 --> 00:17:08,619
So if I pick this age, they will be cycler, not.

289
00:17:10,630 --> 00:17:14,050
There will be no cycle, so you can pick this one.

290
00:17:16,339 --> 00:17:19,579
There will be no second, so you can pick this eight.

291
00:17:22,160 --> 00:17:23,740
Now I've done it, this is it.

292
00:17:24,140 --> 00:17:25,720
So can I pick this?

293
00:17:26,510 --> 00:17:31,070
No, you cannot pick this way because in that case, there will be a cycle introduced.

294
00:17:31,370 --> 00:17:33,290
So you cannot pick it here.

295
00:17:35,850 --> 00:17:42,900
Now, hear, what we have seen is if you would have if you take it first, then you cannot pick this

296
00:17:42,910 --> 00:17:43,160
age.

297
00:17:43,420 --> 00:17:44,980
OK, so what is happening here?

298
00:17:45,000 --> 00:17:48,540
I took this age then I'm not able to pick this age.

299
00:17:49,020 --> 00:17:51,120
Right, because they will be introduced.

300
00:17:51,660 --> 00:17:53,110
No, if I did the opposite.

301
00:17:53,130 --> 00:17:59,600
If I pick this age first and this age later, then I cannot pick this age, because in that case also

302
00:17:59,610 --> 00:18:00,750
they will be a cycle formed.

303
00:18:01,050 --> 00:18:02,610
So here they are.

304
00:18:02,610 --> 00:18:04,910
Possibility that to a and be there.

305
00:18:05,550 --> 00:18:07,870
So in that case to a mouse, they will be there.

306
00:18:09,390 --> 00:18:14,340
So first, let us finish this problem, then I will discuss this, that there are two and possible in

307
00:18:14,340 --> 00:18:14,840
this case.

308
00:18:15,330 --> 00:18:18,350
So after the minimum value is ten, so can I pick ten?

309
00:18:18,900 --> 00:18:21,120
So if you will pick ten, what will happen?

310
00:18:21,450 --> 00:18:23,340
If you will pick this edge?

311
00:18:24,450 --> 00:18:27,180
If you will pick this age, then they will be introduced.

312
00:18:27,180 --> 00:18:33,210
How this, then this, then this, then this and then this.

313
00:18:33,510 --> 00:18:35,160
So you cannot pick 10.

314
00:18:36,180 --> 00:18:39,060
So your MSA will look like this zero.

315
00:18:40,580 --> 00:18:42,260
Then when?

316
00:18:43,390 --> 00:18:44,260
Then three.

317
00:18:46,250 --> 00:18:47,060
Thenceforward.

318
00:18:49,970 --> 00:18:50,600
Then to.

319
00:18:52,600 --> 00:18:53,530
Then six.

320
00:18:54,860 --> 00:19:02,690
And then five, so this is you're one of the minimum spending, three, you are other minimum spending

321
00:19:02,840 --> 00:19:04,430
can be zero.

322
00:19:05,790 --> 00:19:06,180
When?

323
00:19:08,680 --> 00:19:09,220
Three.

324
00:19:10,140 --> 00:19:10,770
For.

325
00:19:12,040 --> 00:19:12,430
To.

326
00:19:15,430 --> 00:19:16,750
Six, five.

327
00:19:18,510 --> 00:19:20,760
So what do you do, you will pick this.

328
00:19:25,840 --> 00:19:31,150
See, I told you, these are the same, so if you will pick this, you are not able to pick this.

329
00:19:31,390 --> 00:19:33,850
If you pick this first, then you are not able to pick this.

330
00:19:33,880 --> 00:19:36,370
So there are two many spanning, three possible.

331
00:19:37,630 --> 00:19:37,960
Right.

332
00:19:38,260 --> 00:19:40,050
So here I have it.

333
00:19:40,060 --> 00:19:42,230
And here also I have it addressed.

334
00:19:42,250 --> 00:19:45,880
All the values that same as all the values are saying this is five.

335
00:19:45,890 --> 00:19:46,560
This is three.

336
00:19:46,960 --> 00:19:47,920
This is seven.

337
00:19:49,080 --> 00:19:53,080
So he decides to listen to the as to the cease fire.

338
00:19:53,130 --> 00:19:55,620
If this is three, this is one.

339
00:19:55,620 --> 00:19:56,460
This is one.

340
00:19:56,880 --> 00:19:59,210
This is two and this is two.

341
00:19:59,490 --> 00:20:01,590
So there are two more possible.

342
00:20:01,590 --> 00:20:03,470
And both have the same cost.

343
00:20:05,370 --> 00:20:09,850
Both have the same cost, because the only thing that is changing is basically this edge.

344
00:20:10,320 --> 00:20:11,310
So this is it.

345
00:20:11,580 --> 00:20:14,150
And this edge also has a weight of it.

346
00:20:14,490 --> 00:20:18,890
So there are two made possible in this example.

347
00:20:19,290 --> 00:20:19,650
Right.

348
00:20:20,490 --> 00:20:22,650
So again, you can see how many nodes out there.

349
00:20:22,800 --> 00:20:26,860
One, two, three, four, five, six, seven, seven nodes are there.

350
00:20:26,880 --> 00:20:29,520
So how many Edgett should be put into them in spending?

351
00:20:29,520 --> 00:20:29,760
Three.

352
00:20:30,180 --> 00:20:31,850
Six edges should be there.

353
00:20:31,860 --> 00:20:36,750
You can count one, two, three, four, five and six.

354
00:20:37,170 --> 00:20:41,700
So that is you spending three to minimize spending are possible in this case.

355
00:20:42,360 --> 00:20:42,800
Right.

356
00:20:43,760 --> 00:20:49,290
So I hope you have understood what this critical algorithm, how Kruskal algorithm works.

357
00:20:50,790 --> 00:20:54,380
So algorithm, what is the difficult step to implement?

358
00:20:55,920 --> 00:20:59,730
I think this step is pretty much simple, right?

359
00:21:00,330 --> 00:21:04,730
This step is very simple, sort of the edges on both sides of it.

360
00:21:05,190 --> 00:21:06,690
So this is very, very simple.

361
00:21:07,080 --> 00:21:10,800
The difficult task in Kruskal algorithm is basically this.

362
00:21:11,790 --> 00:21:18,030
You are picking the edge and then you need to check whether after picking the edge, there is cycle

363
00:21:18,030 --> 00:21:18,460
or not.

364
00:21:18,870 --> 00:21:24,840
So basically the problem here is we should have an algorithm for cycle detection.

365
00:21:26,150 --> 00:21:30,920
Right, we must have one algorithm for cycle detection.

366
00:21:32,970 --> 00:21:39,090
Again, I'm repeating myself in there are two parts, first, you need to sort the edges, then what

367
00:21:39,210 --> 00:21:44,880
to do, you will pick edge, you will pick this that you will pick the sorted edges one by one, and

368
00:21:44,880 --> 00:21:47,520
then you will check whether there is a cycle present or not.

369
00:21:47,970 --> 00:21:50,220
So we need this algorithm.

370
00:21:50,250 --> 00:21:54,930
If we have this algorithm cycle detection, then we can implement algorithm.

371
00:21:55,170 --> 00:21:56,200
Do you agree or not?

372
00:21:56,550 --> 00:21:57,690
Yes, you should agree.

373
00:21:57,990 --> 00:21:58,320
Right.

374
00:21:58,740 --> 00:22:05,160
So the problem is we should have an algorithm for cycle detection and graph.

375
00:22:05,430 --> 00:22:05,850
Right.

376
00:22:08,040 --> 00:22:16,530
So in next video, we will discuss how we can use how we can have an algorithm for cycle detection and

377
00:22:16,530 --> 00:22:19,140
the name of the algorithm is basically disjointed.

378
00:22:21,370 --> 00:22:28,710
We can use this joint set for cycle detection, so in next video, we will be discussing Disjoined said,

379
00:22:29,320 --> 00:22:29,600
right.

380
00:22:30,400 --> 00:22:32,320
So this is it from this video, guys.

381
00:22:33,010 --> 00:22:34,430
I will see you in the next one.

382
00:22:34,930 --> 00:22:35,440
Thank you.