1
00:00:00,390 --> 00:00:01,080
Hi, everyone.

2
00:00:01,110 --> 00:00:07,200
So in this video, we are going to discuss the call for the Kruskal algorithm for finding the medium

3
00:00:07,200 --> 00:00:07,840
spanning tree.

4
00:00:08,220 --> 00:00:16,320
So what is Google algorithm will take as input, so it will take graph as input and what is the approach

5
00:00:16,320 --> 00:00:17,280
that we have discussed?

6
00:00:17,550 --> 00:00:24,840
So what we need to do for each vertex, we will need to call the Miksad function that we have discussed

7
00:00:24,840 --> 00:00:25,590
this many times.

8
00:00:25,930 --> 00:00:32,520
We will call the Miksad function for every vertex and then what we need to do, we need to sort the

9
00:00:32,520 --> 00:00:35,610
edges in increasing order of which.

10
00:00:36,450 --> 00:00:36,900
Right.

11
00:00:37,110 --> 00:00:40,770
We need to start and then we will pick each one by one.

12
00:00:41,520 --> 00:00:43,510
And Edge should not make cycle.

13
00:00:44,490 --> 00:00:46,200
So what is this function done?

14
00:00:46,500 --> 00:00:50,680
So this function will written list of edges in the minimum spanning tree.

15
00:00:51,480 --> 00:00:55,650
So currently in the spanning three, how many pages are there?

16
00:00:55,680 --> 00:01:00,380
So obviously this set is basically empty.

17
00:01:00,630 --> 00:01:02,270
We do not have any edges yet.

18
00:01:02,460 --> 00:01:05,900
So we are going to read the list of ideas, but currently we don't have any idea.

19
00:01:05,940 --> 00:01:14,610
So what we need to do for each edge, basically we will pick each edge and where we can see all the

20
00:01:15,030 --> 00:01:18,000
edges are basically sorted in increasing order of the weights.

21
00:01:18,210 --> 00:01:24,080
So we are going to pick each edge inside determiner right of the manner of bits.

22
00:01:24,420 --> 00:01:27,810
So we are picking each vertex, you and vertex.

23
00:01:27,810 --> 00:01:31,860
We what we need to do, we need to find out the representative element of the set.

24
00:01:32,370 --> 00:01:37,140
So here we are trying to find the representative element.

25
00:01:40,110 --> 00:01:46,590
So X is the representative element for Vertex you, why is the representative element for Vertex V,

26
00:01:47,040 --> 00:01:54,780
if X and Y they are different, different means they belong to different said, they belong to different

27
00:01:54,780 --> 00:01:55,860
connected component.

28
00:01:56,370 --> 00:02:03,150
If they belong to different connected component, then this edge is safe, this X is safe, this edge

29
00:02:03,150 --> 00:02:04,550
will not create cycle.

30
00:02:05,070 --> 00:02:09,570
So since this edge will not cycle so we can keep these two sets.

31
00:02:09,930 --> 00:02:13,800
So we need to club the cells X and Y, right.

32
00:02:13,800 --> 00:02:17,010
X and Y are the representative element for their corresponding sets.

33
00:02:17,250 --> 00:02:19,020
So we are calling unión function.

34
00:02:19,440 --> 00:02:22,770
So we are going to keep them and what else.

35
00:02:22,800 --> 00:02:27,180
So this edge will be the part of our M. spanning three.

36
00:02:27,660 --> 00:02:32,030
So I will add this edge to our minimum spanning preset.

37
00:02:32,070 --> 00:02:33,750
So say it was empty.

38
00:02:33,930 --> 00:02:35,790
Now it will contain this edge.

39
00:02:36,630 --> 00:02:40,410
And finally then we will pick each and every edge.

40
00:02:40,410 --> 00:02:41,880
We will come out of this loop.

41
00:02:41,880 --> 00:02:46,380
We will return misti MSD containing the set of edges.

42
00:02:46,890 --> 00:02:47,360
Right.

43
00:02:47,460 --> 00:02:54,930
So here I have written for clarity that we need to pick the edge only when they are in different set

44
00:02:55,140 --> 00:02:59,940
so that cycle will not form so that there is no cycle.

45
00:03:00,120 --> 00:03:00,570
Right.

46
00:03:00,810 --> 00:03:04,050
So this is the complete code for Kruskal algorithm.

47
00:03:04,890 --> 00:03:05,340
Right.

48
00:03:05,850 --> 00:03:07,960
So this is it from this video.

49
00:03:07,980 --> 00:03:10,590
Guys, if you have any doubt in the code, do let me know.

50
00:03:10,860 --> 00:03:11,640
I will help you.

51
00:03:11,880 --> 00:03:14,970
So that's all that I want to discuss in this video.

52
00:03:15,150 --> 00:03:16,590
I will see you in the next one.

53
00:03:16,590 --> 00:03:17,190
Thank you.