در این مطلب، ویدئو مرتب سازی توپولوژیکی از طریق الگوریتم حذف منبع در پایتون با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:11:57
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,240 –> 00:00:01,839
بنابراین در آموزش امروز ما قصد داریم در
2
00:00:01,839 –> 00:00:03,760
مورد نظریه گراف ها را پوشش
3
00:00:03,760 –> 00:00:06,080
دهیم، بنابراین بیایید به مبحث بعدی
4
00:00:06,080 –> 00:00:07,759
بپردازیم، اما قبل از آن می توانید
5
00:00:07,759 –> 00:00:10,960
به یک مخزن بروید و
6
00:00:10,960 –> 00:00:12,799
تمام کدهای موجود در پایتون را
7
00:00:12,799 –> 00:00:13,120
8
00:00:13,120 –> 00:00:15,519
قبل از قبل از این آموزش دانلود کنید، بنابراین اجازه دهید
9
00:00:15,519 –> 00:00:17,199
با آموزش امروز شروع کنید
10
00:00:17,199 –> 00:00:18,960
پس آموزش امروز ما قصد داریم در
11
00:00:18,960 –> 00:00:20,640
مورد مرتب سازی توپولوژیکی بیاموزیم
12
00:00:20,640 –> 00:00:23,119
بنابراین سیم مرتب سازی توپولوژیکی یک
13
00:00:23,119 –> 00:00:24,480
الگوریتم حذف منبع
14
00:00:24,480 –> 00:00:26,640
بنابراین اساساً الگوریتم حذف
15
00:00:26,640 –> 00:00:28,320
منبع تکنیکی برای پیاده سازی مرتب سازی توپولوژیکی است
16
00:00:28,320 –> 00:00:29,199
17
00:00:29,199 –> 00:00:32,399
بنابراین قبل از اینکه به مرتب سازی توپولوژیکی ادامه
18
00:00:32,399 –> 00:00:34,960
دهیم باید چند نکته را به خاطر بسپاریم که
19
00:00:34,960 –> 00:00:36,239
گراف باید
20
00:00:36,239 –> 00:00:40,000
dac
21
00:00:40,000 –> 00:00:43,360
باشد که
22
00:00:43,360 –> 00:00:47,200
جهت دار و غیر چرخه ای باشد، بنابراین اساساً باید جهت دار باشد و یک چرخه
23
00:00:47,200 –> 00:00:49,120
بنابراین اساساً گراف باید
24
00:00:49,120 –> 00:00:50,640
ابتدا یک گراف جهت دهی شود
25
00:00:50,640 –> 00:00:54,000
و باید یک چرخه باشد و این
26
00:00:54,000 –> 00:00:56,399
مرتب سازی توپولوژیکی برای هر یال u بودن به چه معناست.
27
00:00:56,399 –> 00:00:57,280
28
00:00:57,280 –> 00:00:59,760
در ترتیب نمودار قبل از v خواهد آمد،
29
00:00:59,760 –> 00:01:00,879
30
00:01:00,879 –> 00:01:03,680
بنابراین، یک اصطلاح به نام
31
00:01:03,680 –> 00:01:04,479
درجه داریم
32
00:01:04,479 –> 00:01:07,520
که یال های ورودی روی گره است و
33
00:01:07,520 –> 00:01:08,960
یک عبارت نیز وجود دارد.
34
00:01:08,960 –> 00:01:10,960
درجاتی که لبه های خروجی
35
00:01:10,960 –> 00:01:12,560
نت را فراخوانی کرد، اما
36
00:01:12,560 –> 00:01:16,080
در طول مرتب سازی توپولوژیکی با آن سروکار نداریم، بنابراین
37
00:01:16,080 –> 00:01:17,759
باید سه نقطه را به خاطر بسپاریم که ابتدا
38
00:01:17,759 –> 00:01:19,759
باید جهت دار و غیر چرخه ای باشد،
39
00:01:19,759 –> 00:01:22,080
سپس برای هر یال u تا v u
40
00:01:22,080 –> 00:01:24,000
قبل از b در ترتیب قرار می گیرد. از نمودار
41
00:01:24,000 –> 00:01:26,240
و این ترتیب به عنوان
42
00:01:26,240 –> 00:01:29,439
مرتب سازی توپولوژیکی یا مرتب سازی توپولوژیکی شناخته می شود
43
00:01:29,439 –> 00:01:31,520
و در درجه یال های ورودی روی
44
00:01:31,520 –> 00:01:32,799
گره خوب است،
45
00:01:32,799 –> 00:01:35,600
بنابراین بیایید به جلوتر برویم، اکنون یک
46
00:01:35,600 –> 00:01:36,320
نمودار
47
00:01:36,320 –> 00:01:37,920
داریم و اکنون الگوریتم حذف منبع را پیاده سازی می کنیم،
48
00:01:37,920 –> 00:01:40,000
ابتدا باید
49
00:01:40,000 –> 00:01:43,680
گره را با حداقل در گره نگاه کنیم. درجه
50
00:01:43,680 –> 00:01:45,600
تا بتوانید گره را با حداقل درجه شناسایی کنید این
51
00:01:45,600 –> 00:01:46,720
52
00:01:46,720 –> 00:01:50,000
است که گره b است بنابراین گره b را
53
00:01:50,000 –> 00:01:53,439
می گیریم پس
54
00:01:53,439 –> 00:01:56,880
بیایید گره b را در اینجا بنویسیم و گره
55
00:01:56,880 –> 00:01:59,759
b و تمام یال های مرتبط با آن را
56
00:01:59,759 –> 00:02:01,680
حذف کنیم بنابراین در اینجا b
57
00:02:01,680 –> 00:02:04,240
و تمام یال های مرتبط را حذف می کنیم. با آن اکنون
58
00:02:04,240 –> 00:02:04,880
یک
59
00:02:04,880 –> 00:02:08,000
گره داریم با حداقل درجه a، بنابراین بیایید
60
00:02:08,000 –> 00:02:11,440
a را اینجا بنویسیم یا میتوانید
61
00:02:11,440 –> 00:02:13,040
اول بخوانید یا اول درست،
62
00:02:13,040 –> 00:02:14,879
مهم نیست حالا a را حذف میکنیم
63
00:02:14,879 –> 00:02:19,520
و تمام گرههای مرتبط با a
64
00:02:20,840 –> 00:02:23,520
now uh را حذف میکنیم. گره با
65
00:02:23,520 –> 00:02:24,640
حداقل درجه،
66
00:02:24,640 –> 00:02:27,760
بنابراین اساساً اکنون آنچه را که می توانیم درجه را محاسبه
67
00:02:27,760 –> 00:02:28,720
68
00:02:28,720 –> 00:02:32,000
کنیم، فرض کنید
69
00:02:32,000 –> 00:02:36,160
این دارای دو درجه است، این یک
70
00:02:36,160 –> 00:02:40,400
در درجه دارد متأسفم یک
71
00:02:40,400 –> 00:02:42,640
و این دارای درجه صفر است، بنابراین ما d را حذف می کنیم
72
00:02:42,640 –> 00:02:45,360
مانند این روشی است که حذف می کنیم
73
00:02:45,360 –> 00:02:49,120
خوب حالا بیایید حذف کنیم d
74
00:02:49,360 –> 00:02:53,920
و تمام یال های مرتبط با d را
75
00:02:53,920 –> 00:02:57,120
حذف می کنیم مانند
76
00:02:57,120 –> 00:03:00,239
این روند ادامه دارد b a d
77
00:03:00,239 –> 00:03:03,920
اکنون c و e داریم بنابراین در اینجا می
78
00:03:03,920 –> 00:03:06,159
توانید گره با حداقل درجه c را ببینید
79
00:03:06,159 –> 00:03:09,040
سپس c و تمام یال های
80
00:03:09,040 –> 00:03:11,360
مرتبط با c را
81
00:03:11,360 –> 00:03:14,720
اکنون حذف می کنیم. ما
82
00:03:14,720 –> 00:03:18,400
e را در پایان حذف می کنیم، بنابراین قبل از حرکت e به من اجازه می دهد
83
00:03:18,400 –> 00:03:19,280
84
00:03:19,280 –> 00:03:22,640
c را در اینجا بنویسم متاسفم c
85
00:03:22,640 –> 00:03:25,280
و سپس وقتی e را حذف کردم در انتها
86
00:03:25,280 –> 00:03:26,000
e می آید
87
00:03:26,000 –> 00:03:29,280
و بنابراین من e را نیز حذف می کنم، بنابراین این
88
00:03:29,280 –> 00:03:30,000
89
00:03:30,000 –> 00:03:33,599
مرتب سازی توپولوژیکی اصلی نمودار ما است،
90
00:03:33,599 –> 00:03:37,440
بنابراین اینجاست مانند for
91
00:03:37,440 –> 00:03:41,120
اگر h به b تا a بود
92
00:03:41,120 –> 00:03:42,560
، b در ترتیب قبل از
93
00:03:42,560 –> 00:03:44,720
a میآید، بنابراین از این قانون پیروی میکند که اگر یال
94
00:03:44,720 –> 00:03:45,680
95
00:03:45,680 –> 00:03:47,760
u تا v وجود داشته باشد، u در ترتیب نمودار قبل از v خواهد آمد.
96
00:03:47,760 –> 00:03:49,599
97
00:03:49,599 –> 00:03:52,720
این مرتبسازی توپولوژیکی است،
98
00:03:52,720 –> 00:03:55,840
بنابراین مرتبسازی توپولوژیکی اساساً یک خط است
99
00:03:55,840 –> 00:03:56,799
مرتب سازی گوش
100
00:03:56,799 –> 00:03:59,920
و ما سعی می کنیم این u را در یک
101
00:03:59,920 –> 00:04:02,480
زمان خطی حل کنیم، بنابراین اساساً آنچه را که می خواهیم
102
00:04:02,480 –> 00:04:03,280
103
00:04:03,280 –> 00:04:05,280
اولین جستجوی وسعت اجرا کنیم که از نظر زمانی
104
00:04:05,280 –> 00:04:07,120
خطی است و پیچیدگی زمانی
105
00:04:07,120 –> 00:04:07,760
106
00:04:07,760 –> 00:04:12,640
o بزرگ b به علاوه e خواهد بود بنابراین پیچیدگی زمانی
107
00:04:12,640 –> 00:04:16,160
برابر با بزرگ o v است. بعلاوه e
108
00:04:16,160 –> 00:04:20,798
بنابراین ما می خواهیم از bfs استفاده کنیم، پس
109
00:04:20,798 –> 00:04:24,960
اجازه دهید
110
00:04:24,960 –> 00:04:29,040
نمونه آزمایشی این نمودار را به شما نشان دهم،
111
00:04:29,040 –> 00:04:31,440
بله، این مورد آزمایشی نمودار ما
112
00:04:31,440 –> 00:04:33,360
است، این همان مورد مشابهی است
113
00:04:33,360 –> 00:04:36,320
که من داشتم، این همان نموداری است که
114
00:04:36,320 –> 00:04:37,759
نشان داده بودم شما
115
00:04:37,759 –> 00:04:41,120
به طوری که a به c a به d
116
00:04:41,120 –> 00:04:44,000
b دو a b دو d است بنابراین در اینجا می توانید a به
117
00:04:44,000 –> 00:04:44,720
c a به d
118
00:04:44,720 –> 00:04:48,479
b دو a b d سپس c two e را ببینید بنابراین ما c
119
00:04:48,479 –> 00:04:51,680
two e و d دو c و d two e داریم بنابراین
120
00:04:51,680 –> 00:04:54,000
اکنون همه شرایط را برآورده می کند بیایید
121
00:04:54,000 –> 00:04:55,759
این الگوریتم را پیادهسازی کنیم،
122
00:04:55,759 –> 00:04:57,840
بنابراین من الگوی
123
00:04:57,840 –> 00:04:59,840
نحوه گرفتن ورودی از نمودار
124
00:04:59,840 –> 00:05:02,400
را ساختم تا در زمان صرفهجویی کنیم و بتوانیم
125
00:05:02,400 –> 00:05:03,919
روی بخش منطقی تمرکز کنیم،
126
00:05:03,919 –> 00:05:07,360
بنابراین بیایید با
127
00:05:07,360 –> 00:05:08,240
کد
128
00:05:08,240 –> 00:05:11,680
ادامه دهیم تا مانند ابتدا اجرا کنیم که
129
00:05:11,680 –> 00:05:12,560
130
00:05:12,560 –> 00:05:16,160
باید یک توجه داشته باشید درجه بنابراین
131
00:05:16,160 –> 00:05:18,000
درجه باید گره
132
00:05:18,000 –> 00:05:19,520
درجه و
133
00:05:19,520 –> 00:05:22,479
اینجا را بسازیم می