1
00:00:00,960 --> 00:00:01,680
Hi, everyone.

2
00:00:01,710 --> 00:00:08,580
So in this video, we are going to learn about topological saat and why topological art is important.

3
00:00:08,820 --> 00:00:14,580
So in recent times, what is happening is companies started asking questions about topological thought.

4
00:00:15,090 --> 00:00:20,370
They will not directly ask you to write the code for topological thought, explained a logical thought.

5
00:00:20,590 --> 00:00:25,440
They will give you a statement and you have to think yourself that topological thought can be used here.

6
00:00:25,770 --> 00:00:28,030
So what will it really look like?

7
00:00:28,320 --> 00:00:30,830
So you will be given basically Dagg.

8
00:00:31,590 --> 00:00:32,729
So what is that?

9
00:00:32,910 --> 00:00:37,190
Bagis basically directed cyclic graph.

10
00:00:38,250 --> 00:00:43,650
So they will give you are directed outside calligraphy and they will ask you to print something, to

11
00:00:43,650 --> 00:00:48,340
output something, and you need to figure out whether topological so can be used or not.

12
00:00:48,540 --> 00:00:52,700
So the example can be you want to install one software.

13
00:00:52,830 --> 00:00:58,000
Let's say the name of the software is software if you want to install software.

14
00:00:58,330 --> 00:01:05,489
But this software five has a dependency on software for that means before installing Software five,

15
00:01:05,760 --> 00:01:12,400
you need to install software for and software five depends on software for.

16
00:01:12,570 --> 00:01:15,960
So that's why this arrow this directed at.

17
00:01:15,960 --> 00:01:17,040
All right.

18
00:01:17,040 --> 00:01:24,600
I'm explaining myself again to install software, if it requires prerequisite, is that you must install

19
00:01:24,600 --> 00:01:32,550
software for to install software for the prerequisite is that you must install software three.

20
00:01:35,400 --> 00:01:45,390
To install software three, you must install Software zero, prerequisite is that you must have software

21
00:01:45,390 --> 00:01:51,330
zero four for not only software three, you need one more software.

22
00:01:51,330 --> 00:01:58,410
One more prerequisite is there that you need software to to install software to.

23
00:01:59,250 --> 00:02:04,470
The prerequisite is that you must have software one with you.

24
00:02:05,190 --> 00:02:11,880
Similarly, Software five not only depends on software for it also depends on software three.

25
00:02:13,770 --> 00:02:16,470
So that's the problem statement I'm repeating myself.

26
00:02:16,830 --> 00:02:23,580
We want to install software five and the prerequisite is that you must have software for it and software

27
00:02:23,580 --> 00:02:24,480
to be installed.

28
00:02:25,080 --> 00:02:32,620
OK, for software for the prerequisite is that you must have software installed and software to install

29
00:02:32,620 --> 00:02:36,030
the OK for installing software to.

30
00:02:36,030 --> 00:02:40,960
The prerequisite is that you must install software for installing software three.

31
00:02:40,980 --> 00:02:47,460
The prerequisite is that you must install software zero and the software one and software zero.

32
00:02:47,490 --> 00:02:48,960
They are basically independent.

33
00:02:49,230 --> 00:02:51,510
They can be installed independently, right.

34
00:02:51,510 --> 00:02:53,330
They do not have any other prerequisite.

35
00:02:53,520 --> 00:02:57,000
So now the question is you need to print the order.

36
00:02:57,750 --> 00:03:02,010
You need to print the order in which you will install the software.

37
00:03:03,060 --> 00:03:03,490
Right.

38
00:03:03,930 --> 00:03:05,040
You need to print.

39
00:03:05,040 --> 00:03:06,210
You need to figure out.

40
00:03:06,330 --> 00:03:07,350
You need to figure it out.

41
00:03:07,350 --> 00:03:11,840
And you need to print the order in which you will be installing the software.

42
00:03:12,210 --> 00:03:15,750
If you will directly install Software five, the installation will fail.

43
00:03:16,260 --> 00:03:18,360
It will take three and four not present.

44
00:03:18,840 --> 00:03:24,660
If you directly install software for it will say it will fail and it will say software tool and software,

45
00:03:24,870 --> 00:03:25,500
not phone.

46
00:03:25,620 --> 00:03:30,150
If you install software to it will say software were not found and it will fail.

47
00:03:30,420 --> 00:03:35,470
Similarly, if you directly try to install software tree, it will fail and it will say software zero

48
00:03:35,490 --> 00:03:36,060
not found.

49
00:03:36,570 --> 00:03:39,240
So I hope you have understood the problem statement.

50
00:03:39,660 --> 00:03:40,080
Right.

51
00:03:40,380 --> 00:03:47,790
And what will be the order so you can install software zero first, then one, then two, then three,

52
00:03:47,790 --> 00:03:54,540
then four and then five or the other order can be you can first install software one, then zero because

53
00:03:54,540 --> 00:03:56,220
one and zero are basically independent.

54
00:03:56,220 --> 00:03:56,550
Right.

55
00:03:57,300 --> 00:04:00,900
Then you can install two, three, four and five.

56
00:04:01,680 --> 00:04:05,740
The other order can be if you are installing one first then zero.

57
00:04:05,880 --> 00:04:09,060
So when they are independent so they order doesn't matter.

58
00:04:09,060 --> 00:04:09,380
Right.

59
00:04:09,390 --> 00:04:15,300
You can install zero first or you can install one first or you can install zero first, then you can

60
00:04:15,300 --> 00:04:20,640
install three to four, five because three and two, they are also independent.

61
00:04:20,640 --> 00:04:22,110
They are not related to each other.

62
00:04:22,110 --> 00:04:22,500
Right.

63
00:04:24,210 --> 00:04:26,670
So you need to print this order.

64
00:04:26,940 --> 00:04:28,650
You don't need to print any one of them.

65
00:04:29,310 --> 00:04:32,310
All three are correct and there can be many more orders.

66
00:04:32,310 --> 00:04:32,730
Right.

67
00:04:33,840 --> 00:04:36,780
So what do you need to print any one of them?

68
00:04:38,610 --> 00:04:40,260
You need to print any one of them.

69
00:04:40,260 --> 00:04:43,320
And I think they will be one more order, which is possible.

70
00:04:43,320 --> 00:04:45,630
That is zero and one zero one.

71
00:04:45,630 --> 00:04:46,530
They are independent.

72
00:04:46,530 --> 00:04:47,430
They can be installed.

73
00:04:47,700 --> 00:04:51,930
Once 011 are installed, then you can install twenty eight.

74
00:04:52,260 --> 00:04:54,570
Once zero is installed, you can install three.

75
00:04:55,110 --> 00:05:01,560
Similarly, once software one is installed, you can install software two and two and three are installed.

76
00:05:01,560 --> 00:05:06,340
So you can install software for once, software for any of the three and install it.

77
00:05:06,360 --> 00:05:08,010
Then you can install software five.

78
00:05:08,760 --> 00:05:15,960
So I think there are four possible ways in which we can install this software and we need to print any

79
00:05:15,960 --> 00:05:20,010
one of them because all the files are correct so we can print any one of them.

80
00:05:20,010 --> 00:05:26,580
I am explaining myself again, let's say for this example, Software Zero is independent so I can install

81
00:05:26,580 --> 00:05:26,730
it.

82
00:05:27,000 --> 00:05:32,700
Software one is an independent so I can install it so that he can be installed because of the zero is

83
00:05:32,700 --> 00:05:35,070
installed in our software can be installed.

84
00:05:35,310 --> 00:05:38,250
Software too can be installed because of the awareness there.

85
00:05:38,550 --> 00:05:43,770
So you can install software to since we have software to software tree so we can install software for

86
00:05:44,160 --> 00:05:44,610
correct.

87
00:05:44,850 --> 00:05:48,540
Since we have software three and four installed so we can install software five.

88
00:05:48,660 --> 00:05:49,110
Correct.

89
00:05:49,500 --> 00:05:51,300
So all the orders are correct.

90
00:05:51,300 --> 00:05:53,190
We just need to print any one of them.

91
00:05:53,310 --> 00:05:58,800
And this graph, this graph is basically direct data graph and acyclic.

92
00:05:58,800 --> 00:06:00,840
There is no cyclic present in this graph.

93
00:06:01,230 --> 00:06:03,870
That means topological so can be used here.

94
00:06:04,170 --> 00:06:06,960
So if you see this is basically one sorting order.

95
00:06:08,340 --> 00:06:11,940
This is we can say this is basically one type of sorting only.

96
00:06:11,940 --> 00:06:12,300
Right.

97
00:06:12,720 --> 00:06:14,550
We are outputting inside Travie.

98
00:06:15,090 --> 00:06:19,950
So that's where the name of the algorithm is topological and how this algorithm works.

99
00:06:20,310 --> 00:06:26,340
So let's let's try to understand how the topological sort will give us the desired output.

100
00:06:27,360 --> 00:06:30,150
So let's consider this example only.

101
00:06:31,200 --> 00:06:33,300
So let me write it again here.

102
00:06:34,180 --> 00:06:41,740
And then we will try to understand how the topological sort will work, so let's say I have I have one.

103
00:06:42,520 --> 00:06:44,920
So for two.

104
00:06:46,720 --> 00:06:56,200
Or the other way in which this problem can be fixed is basically, let me tell you so let's say for

105
00:06:56,200 --> 00:07:01,270
doing for doing a course for and rolling in goes five.

106
00:07:01,390 --> 00:07:08,410
You need to first complete goes for and you need to force complete goals.

107
00:07:08,410 --> 00:07:18,280
Three Sokol's three and four are basically the prerequisite for enrolling in goals five, four and rolling

108
00:07:18,280 --> 00:07:26,230
in goals for you need to first complete goals three as well as you need to first complete goals to.

109
00:07:29,280 --> 00:07:39,060
For enrolling and completing course to unit first and rule and complete goals, one for completing,

110
00:07:39,420 --> 00:07:45,330
three for enrolling and completing all three, you need to first complete and end all.

111
00:07:45,330 --> 00:07:47,910
You need to first enroll and complete course zero.

112
00:07:48,450 --> 00:07:54,270
Now the question is print the order in which you will enroll and complete the course.

113
00:07:54,720 --> 00:07:59,130
So again, this is directed acyclic graph so topological.

114
00:07:59,130 --> 00:08:02,520
So it will be used here and how topological sought will be used here.

115
00:08:02,850 --> 00:08:09,710
So what will do given the graph, given a graph, first of all, we will find out in the gray area.

116
00:08:10,050 --> 00:08:14,970
So we will populate one in the grey area in degree.

117
00:08:17,100 --> 00:08:23,140
So for Vertex Zero, Vertex one, vertex two, vertex three, vertex four and Vertex five.

118
00:08:23,970 --> 00:08:27,740
Let's try to bring in degree values.

119
00:08:28,320 --> 00:08:30,060
So what do I mean by and degree.

120
00:08:30,270 --> 00:08:36,750
So for this node, this, this, this, these are incoming arrows.

121
00:08:37,350 --> 00:08:39,570
These are outgoing arrows.

122
00:08:39,750 --> 00:08:43,610
So in degree is three, our degree is two.

123
00:08:44,070 --> 00:08:52,020
So this is in degree for this node, which is three, because three arrows are directed towards this.

124
00:08:52,470 --> 00:08:54,290
Two is basically our degree.

125
00:08:55,770 --> 00:08:58,560
So two arrows are going out of it.

126
00:08:58,560 --> 00:08:59,580
So that's why that's that.

127
00:08:59,670 --> 00:09:00,540
That is our.

128
00:09:01,230 --> 00:09:05,040
So we need to fill the in degree value for each of the vertex.

129
00:09:05,700 --> 00:09:12,870
So given a graph we can figure out in degree, for example, forecourts zero in degrees, zero for course,

130
00:09:12,870 --> 00:09:21,390
one in degree is zero for close to in degree is one for corsetry in degree is one four calls for in

131
00:09:21,390 --> 00:09:23,350
degree is two four calls.

132
00:09:23,400 --> 00:09:25,170
Five in degree is two.

133
00:09:25,590 --> 00:09:26,040
Right.

134
00:09:26,280 --> 00:09:32,970
So we can fill this in degree array because the graph is given to us so we can easily populate the values

135
00:09:32,970 --> 00:09:33,270
here.

136
00:09:33,810 --> 00:09:34,260
Correct.

137
00:09:34,590 --> 00:09:42,510
So after filling the in degrees here, the main thing to notice is the main important point to notice

138
00:09:42,510 --> 00:09:49,530
this problem is basically see the vertex that are having in degree as zero.

139
00:09:50,370 --> 00:09:59,090
That means they are independent, they are independent, they can be picked up and completed late to

140
00:09:59,130 --> 00:10:01,830
cause zero course when they have in degrees zero.

141
00:10:02,010 --> 00:10:05,070
That means that do not they do not have any prerequisite.

142
00:10:05,370 --> 00:10:08,100
You can directly enroll in this course and finish this course.

143
00:10:08,460 --> 00:10:12,260
That is the main logic behind this problem, behind that of a logical thought.

144
00:10:12,300 --> 00:10:16,500
So what you will do after figuring out the degree, you will maintain a queue.

145
00:10:16,650 --> 00:10:20,130
And in this queue, this is curate a structure.

146
00:10:20,550 --> 00:10:27,930
In this queue, you will only insert the vertex, which has zero degree, zero in degree.

147
00:10:28,830 --> 00:10:32,580
Basically, this is what I will insert.

148
00:10:32,580 --> 00:10:36,630
I will only insert those vertex which are independent vertex.

149
00:10:37,980 --> 00:10:39,420
Which vertex?

150
00:10:40,560 --> 00:10:42,180
The vertex, which are independent.

151
00:10:42,420 --> 00:10:45,360
So in this case, Vertex Zero and one are independent.

152
00:10:45,360 --> 00:10:52,500
So insert the zero, insert one because they are independent, the rest are dependent, still dependent.

153
00:10:52,500 --> 00:10:56,090
They have, they are values are not zero degrees below zero.

154
00:10:56,100 --> 00:10:57,050
So they are dependent.

155
00:10:57,840 --> 00:10:58,760
Now what will do.

156
00:10:59,100 --> 00:11:02,100
They will run a loop while the queue is not empty.

157
00:11:02,730 --> 00:11:06,630
We will run a loop while the queue is not empty.

158
00:11:08,100 --> 00:11:15,210
So pick the first node and remove it from here and your output will be here.

159
00:11:16,350 --> 00:11:19,830
So pick the first node printed here.

160
00:11:20,670 --> 00:11:21,680
And what we will do?

161
00:11:21,810 --> 00:11:23,990
Go to all the neighbors of zero.

162
00:11:24,450 --> 00:11:25,530
Let me write it here.

163
00:11:25,620 --> 00:11:28,500
Go to all neighbours.

164
00:11:29,550 --> 00:11:30,840
So go to neighbours.

165
00:11:30,840 --> 00:11:33,630
It has only one neighbour, which is three.

166
00:11:34,270 --> 00:11:39,240
It has only one neighbour which is three and reduce their in degree.

167
00:11:41,760 --> 00:11:47,880
So go to three and reduce their in degree by one so it will become zero.

168
00:11:49,140 --> 00:11:55,290
Why I am reducing the in degree because I have completed this thing, I have completed this thing.

169
00:11:55,770 --> 00:11:59,360
So that's why I go to all the neighbours and reduce in degree by one.

170
00:11:59,760 --> 00:12:03,000
So now the degree for three has become zero.

171
00:12:03,600 --> 00:12:05,850
Zero means it is independent.

172
00:12:05,970 --> 00:12:08,520
Independent means it should be present in the queue.

173
00:12:09,540 --> 00:12:18,330
So I will insert in the queue now the next thing pick when printed here.

174
00:12:19,020 --> 00:12:27,650
Go to all the neighbours of one, go to the neighbours of one two and reduce their in degree by.

175
00:12:29,480 --> 00:12:37,160
So reduce what I will do, I am going to complete this course, so that's why I am reducing that degree

176
00:12:37,160 --> 00:12:39,710
by seven so that degree will become zero.

177
00:12:40,100 --> 00:12:42,020
Zero means independent.

178
00:12:42,560 --> 00:12:47,320
Independent means it should be present in the queue because it can now be completed.

179
00:12:47,330 --> 00:12:50,120
So it should be part of queue.

180
00:12:50,570 --> 00:12:55,610
So push to indicate, you know, the next is basically three.

181
00:12:56,540 --> 00:13:00,350
So big three painted here.

182
00:13:00,950 --> 00:13:02,560
Go to the neighbors of three.

183
00:13:03,350 --> 00:13:08,990
So three has two neighbors, four and five.

184
00:13:10,370 --> 00:13:17,630
So reduce in degree by one because I am completed, I have completed corsetry.

185
00:13:19,010 --> 00:13:22,960
So reduce in degree of four by one and five by one.

186
00:13:24,770 --> 00:13:26,390
So it is still one.

187
00:13:26,390 --> 00:13:30,800
So they are not independent, they are not independent means they will not be the part of the queue

188
00:13:30,800 --> 00:13:31,350
right now.

189
00:13:32,420 --> 00:13:36,020
Now the next element is to pick two.

190
00:13:38,060 --> 00:13:39,170
I will complete.

191
00:13:39,170 --> 00:13:42,110
I have enrolled in the course and I have completed this course.

192
00:13:42,680 --> 00:13:46,580
So go to all the neighbors of two, which is neighbor four.

193
00:13:47,420 --> 00:13:51,920
So reduce in degree by one it will become zero.

194
00:13:52,760 --> 00:13:54,620
Zero means independent.

195
00:13:54,860 --> 00:13:56,810
Independent means it can be.

196
00:13:57,080 --> 00:14:03,290
It has to be the part of queue because I can complete I can enroll and complete this course now.

197
00:14:04,580 --> 00:14:05,000
Right.

198
00:14:05,480 --> 00:14:07,010
So four is now a part of.

199
00:14:07,010 --> 00:14:19,100
Q So big four complete for go to all the neighbors of four and reduce their degree by one because I

200
00:14:19,100 --> 00:14:20,330
have completed this course.

201
00:14:20,690 --> 00:14:23,240
So Ford has only one neighbour which is five.

202
00:14:23,510 --> 00:14:29,330
So reduce in degree by one it will become zero zero means independent.

203
00:14:29,600 --> 00:14:31,730
Independent means it will be part of.

204
00:14:31,730 --> 00:14:41,690
Q That is Bush five now big five from here complete five go to all the neighbours of five.

205
00:14:41,690 --> 00:14:43,570
Five doesn't have any neighbour.

206
00:14:44,630 --> 00:14:47,030
Now your queue becomes empty.

207
00:14:47,180 --> 00:14:49,760
So since your queue becomes empty we are done.

208
00:14:49,850 --> 00:14:51,290
And this is your output.

209
00:14:52,580 --> 00:14:54,350
This is our output.

210
00:14:54,530 --> 00:14:55,820
Which is correct.

211
00:14:58,250 --> 00:14:58,670
Right.

212
00:14:59,000 --> 00:15:00,320
This is our output.

213
00:15:00,320 --> 00:15:01,490
Which is correct.

214
00:15:02,180 --> 00:15:07,520
Now your output can change depending how you insert the elements in queue.

215
00:15:07,730 --> 00:15:11,000
For example, 011, they both are independent, right?

216
00:15:11,180 --> 00:15:12,500
They both are independent.

217
00:15:12,500 --> 00:15:15,290
I inserted zero first, then I inserted one.

218
00:15:15,800 --> 00:15:17,420
I could have done the reverse also.

219
00:15:17,810 --> 00:15:22,730
If I inserted one, then I have inserted zero, then output might have been different.

220
00:15:23,030 --> 00:15:25,340
Right, but the output will be correct for char.

221
00:15:25,910 --> 00:15:31,520
So depending how you insert in the queue you will get different, different output.

222
00:15:32,450 --> 00:15:35,180
You may or may not get one single output.

223
00:15:35,780 --> 00:15:40,040
I mean, it may be possible that there is only one possible order.

224
00:15:42,050 --> 00:15:45,260
There is only one possible order and there can be many possible order.

225
00:15:46,520 --> 00:15:46,970
Right.

226
00:15:47,660 --> 00:15:49,430
So any situation can be there.

227
00:15:49,940 --> 00:15:52,580
So in case of when possible order, your output will be correct.

228
00:15:52,580 --> 00:15:57,560
In case of many possible order, the topological sort will give you one of the order, the order in

229
00:15:57,560 --> 00:15:59,930
which you will be inserting the elements in the queue.

230
00:16:00,410 --> 00:16:02,720
So that is how topological works.

231
00:16:03,080 --> 00:16:08,960
And this topological thought is really important because it is getting off in almost all of the interviews

232
00:16:08,960 --> 00:16:09,260
now.

233
00:16:09,410 --> 00:16:13,700
So be sure you've watched this video before, preparing for an interview.

234
00:16:13,880 --> 00:16:17,870
So in the next video, we will be writing the pseudocode for the topological sort.

235
00:16:18,290 --> 00:16:19,930
So I will see you in the next one.

236
00:16:20,450 --> 00:16:21,020
Thank you.