در این مطلب، ویدئو برنامه پایتون برای عملیات حذف گراف | حذف گره | فهرست مجاورت | ساختار داده ها با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:13:32
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,320 –> 00:00:02,080
سلام بچه ها و به کانال یوتیوب آکادمی amulya خوش آمدید
2
00:00:02,080 –> 00:00:03,760
3
00:00:03,760 –> 00:00:05,520
ما در مورد عملیات حذف گراف بحث می کردیم
4
00:00:05,520 –> 00:00:07,839
و در آموزش قبلی
5
00:00:07,839 –> 00:00:09,200
تابعی برای
6
00:00:09,200 –> 00:00:11,360
عملیات حذف گره و همچنین عملیات حذف
7
00:00:11,360 –> 00:00:12,400
لبه
8
00:00:12,400 –> 00:00:15,360
با استفاده از نمایش ماتریس
9
00:00:15,360 –> 00:00:17,119
مجاورت نوشتیم در ادامه بیایید یک تابع بنویسیم که
10
00:00:17,119 –> 00:00:18,400
این عملیات را با استفاده از
11
00:00:18,400 –> 00:00:21,359
لیست مجاورت انجام دهد. نمایندگی امروز در
12
00:00:21,359 –> 00:00:23,199
این آموزش ما در حال نوشتن تابعی
13
00:00:23,199 –> 00:00:25,920
برای حذف گره داده شده از نمودار
14
00:00:25,920 –> 00:00:29,039
با استفاده از نمایش لیست مجاورت هستیم.
15
00:00:29,039 –> 00:00:31,439
عملیات حذف گره گره داده شده را
16
00:00:31,439 –> 00:00:32,719
از نمودار
17
00:00:32,719 –> 00:00:35,760
حذف می کند و همچنین یال های متصل
18
00:00:35,760 –> 00:00:36,160
به
19
00:00:36,160 –> 00:00:39,120
آن گره داده شده را حذف می کند، به عنوان مثال اگر بخواهم
20
00:00:39,120 –> 00:00:39,680
21
00:00:39,680 –> 00:00:42,480
گره c را در اینجا حذف کنید اگر عملیات را نام ببرم
22
00:00:42,480 –> 00:00:44,559
delete node در گره
23
00:00:44,559 –> 00:00:46,640
c، گره c از نمودار حذف می شود
24
00:00:46,640 –> 00:00:49,200
و همچنین یال های متصل به
25
00:00:49,200 –> 00:00:49,840
c
26
00:00:49,840 –> 00:00:52,320
که این یال است و این یال است، باید
27
00:00:52,320 –> 00:00:53,120
28
00:00:53,120 –> 00:00:56,719
این دو یال را هم اکنون حذف کنیم.
29
00:00:56,719 –> 00:00:58,320
عملیات حذف گره را
30
00:00:58,320 –> 00:01:00,320
انجام دهم چه تغییراتی را باید در
31
00:01:00,320 –> 00:01:02,800
نمایش لیست مجاورت
32
00:01:02,800 –> 00:01:04,479
در اینجا انجام دهم تا فهرست مجاورت
33
00:01:04,479 –> 00:01:07,200
repres عبارتی که از دیکشنری ها استفاده می کنیم
34
00:01:07,200 –> 00:01:09,360
و در کلید فرهنگ لغت
35
00:01:09,360 –> 00:01:11,439
گره های نمودار را نشان می دهد
36
00:01:11,439 –> 00:01:14,320
و مقدار نشان دهنده لیست گره های
37
00:01:14,320 –> 00:01:14,960
مجاور است،
38
00:01:14,960 –> 00:01:19,280
اکنون وقتی گره c را حذف می کنم
39
00:01:19,280 –> 00:01:22,479
اولین قدم این است که باید آن کلید را
40
00:01:22,479 –> 00:01:24,880
از فرهنگ لغت حذف کنیم، بنابراین باید
41
00:01:24,880 –> 00:01:26,080
این را حذف کنم. جفت کلید و مقدار
42
00:01:26,080 –> 00:01:28,720
بنابراین اولین قدم این است که باید این را حذف
43
00:01:28,720 –> 00:01:29,680
44
00:01:29,680 –> 00:01:31,840
کنیم بعد باید اتصال را حذف کنیم
45
00:01:31,840 –> 00:01:34,479
همچنین لبه سمت راست به c متصل است به
46
00:01:34,479 –> 00:01:37,119
همین دلیل باید مقدار
47
00:01:37,119 –> 00:01:38,320
هر کلید را بررسی کنیم
48
00:01:38,320 –> 00:01:40,240
و در اینجا مقدار چیزی نیست جز یک لیست
49
00:01:40,240 –> 00:01:42,960
درست و در آن لیست باید بررسی
50
00:01:42,960 –> 00:01:45,280
کنیم که آیا گره حذف شده که c
51
00:01:45,280 –> 00:01:47,360
است در لیست وجود دارد یا خیر،
52
00:01:47,360 –> 00:01:50,079
اگر c وجود دارد، باید
53
00:01:50,079 –> 00:01:51,680
آن را از لیست حذف کنیم،
54
00:01:51,680 –> 00:01:54,079
به عنوان مثال در اینجا می توانید ببینید ابتدا
55
00:01:54,079 –> 00:01:54,880
باید
56
00:01:54,880 –> 00:01:57,920
مقدار کلید a این لیست را بررسی کنم. مقدار
57
00:01:57,920 –> 00:01:58,719
58
00:01:58,719 –> 00:02:02,079
کلید a است، بنابراین در اینجا c وجود دارد و در اینجا
59
00:02:02,079 –> 00:02:03,680
ما گره c را حذف می
60
00:02:03,680 –> 00:02:05,520
کنیم، به همین دلیل است که باید این را از این لیست حذف کنم،
61
00:02:05,520 –> 00:02:07,200
62
00:02:07,200 –> 00:02:09,119
پس از تکمیل این، باید
63
00:02:09,119 –> 00:02:10,639
کلید بعدی
64
00:02:10,639 –> 00:02:13,520
که b است را بررسی کنم و باید مقدار آن را بررسی کنم.
65
00:02:13,520 –> 00:02:15,120
و باید بررسی کنم آیا c
66
00:02:15,120 –> 00:02:17,440
در اینجا وجود دارد یا نه c وجود ندارد، بنابراین
67
00:02:17,440 –> 00:02:19,200
نیازی به حذف آن از
68
00:02:19,200 –> 00:02:22,560
لیست نیست، بیایید کلید بعدی را بررسی کنیم که d است
69
00:02:22,560 –> 00:02:24,400
.
70
00:02:24,400 –> 00:02:25,920
71
00:02:25,920 –> 00:02:28,000
72
00:02:28,000 –> 00:02:29,599
73
00:02:29,599 –> 00:02:31,840
در مرحله بعد باید کلید بعدی را بررسی کنم باید
74
00:02:31,840 –> 00:02:34,480
مقدار آن را بررسی کنم که آیا c
75
00:02:34,480 –> 00:02:36,400
موجود است یا نه حذف کنید که از
76
00:02:36,400 –> 00:02:37,519
لیست
77
00:02:37,519 –> 00:02:41,200
اکنون می خواهیم تابع
78
00:02:41,200 –> 00:02:44,480
عملیات حذف گره را بنویسیم و در حین
79
00:02:44,480 –> 00:02:46,560
حذف گره باید ذکر کنیم که کدام گره است.
80
00:02:46,560 –> 00:02:48,000
می خواهید حذف کنید
81
00:02:48,000 –> 00:02:49,680
و در حین نوشتن تابع،
82
00:02:49,680 –> 00:02:51,440
مرحله اول این است که باید بررسی کنیم آیا
83
00:02:51,440 –> 00:02:54,400
v در نمودار وجود دارد یا خیر، v
84
00:02:54,400 –> 00:02:56,319
چیزی نیست جز راس یا گره ای که
85
00:02:56,319 –> 00:02:58,319
می خواهم در
86
00:02:58,319 –> 00:03:00,480
صورت وجود آن را از نمودار حذف کنم، پس فقط می توانم
87
00:03:00,480 –> 00:03:02,319
آن را درست حذف کنم. به همین دلیل شرط اول
88
00:03:02,319 –> 00:03:04,800
این است که اگر v وجود ندارد باید بررسی کنیم که آیا v وجود دارد
89
00:03:04,800 –> 00:03:07,200
یا خیر، سپس اگر v وجود داشته باشد، ابتدا
90
00:03:07,200 –> 00:03:09,120
یک پیام چاپ می
91
00:03:09,120 –> 00:03:12,720
کنیم، ابتدا باید
92
00:03:12,720 –> 00:03:16,000
کلید v را از فرهنگ لغت
93
00:03:16,000 –> 00:03:19,040
حذف کنیم و همچنین مقدار آن را باید حذف کنیم.
94
00:03:19,040 –> 00:03:22,480
جفت کلید و مقدار v گره ای که
95
00:03:22,480 –> 00:03:24,080
می خواهم حذف
96
00:03:24,080 –> 00:03:26,879
کنم همانطور که در فرهنگ لغت گفتم هر کلید
97
00:03:26,879 –> 00:03:29,360
گره های گراف را به درستی نشان می
98
00:03:29,360 –> 00:03:31,920
دهد اگر گره v را در
99
00:03:31,920 –> 00:03:32,560
نمودار
100
00:03:32,560 –> 00:03:34,799
حذف می کنید، ابتدا باید آن
101
00:03:34,799 –> 00:03:37,040
جفت ارزش کلید را از فرهنگ لغت حذف کنم و
102
00:03:37,040 –> 00:03:40,959
سپس باید آن را بررسی کنیم مقدار هر
103
00:03:40,959 –> 00:03:41,920
کلید
104
00:03:41,920 –> 00:03:43,920
و ما باید بررسی کنیم که آیا
105
00:03:43,920 –> 00:03:45,599
v در آن لیست وجود دارد
106
00:03:45,599 –> 00:03:47,680
یا خیر، سپس آن را
107
00:03:47,680 –> 00:03:49,120
از لیست
108
00:03:49,120 –> 00:03:51,280
حذف کنیم، در حالی
109
00:03:51,280 –> 00:03:52,560
که گره را
110
00:03:52,560 –> 00:03:55,439
در نمایش لیست مجاورت حذف می کنیم،
111
00:03:55,439 –> 00:03:57,920
خوب است، بنابراین بیایید تابع را
112
00:03:57,920 –> 00:04:00,959
در اینجا بنویسیم. برنامه ما در این برنامه
113
00:04:00,959 –> 00:04:01,840
در اینجا می توانید
114
00:04:01,840 –> 00:04:05,040
یک دیکشنری نمودار فرهنگ لغت را ببینید و در
115
00:04:05,040 –> 00:04:06,720
این برنامه قبلاً
116
00:04:06,720 –> 00:04:09,840
عملیات add node و add edge را
117
00:04:09,840 –> 00:04:12,799
تعریف کرده ایم اکنون در اینجا بعد می خواهیم تابع حذف گره را تعریف کنیم
118
00:04:12,799 –> 00:04:14,080
119
00:04:14,080 –> 00:04:17,600
df حذف گره من
120
00:04:17,600 –> 00:04:19,120
نام تابع را به عنوان حذف گره i می گیرم.
121
00:04:19,120 –> 00:04:20,720
پارامتر را به عنوان v
122
00:04:20,720 –> 00:04:22,639
v گرهی میگیریم که میخواهم آن را
123
00:04:22,639 –> 00:04:24,080
از نمودار حذف کنم
124
00:04:24,080 –> 00:04:26,479
و مرحله بعدی اینجاست که باید
125
00:04:26,479 –> 00:04:27,520
بررسی کنیم آیا
126
00:04:27,520 –> 00:04:31,040
v در نمودار وجود دارد یا نه، بنابراین اگر
127
00:04:31,040 –> 00:04:34,240
در گراف
128
00:04:34,240 –> 00:04:36,320
نیستیم، گراف یک دیسک است. بنابراین، ما در حال
129
00:04:36,320 –> 00:04:37,520
بررسی هستیم که آیا v
130
00:04:37,520 –> 00:04:39,520
گره داده شده در فرهنگ لغت وجود دارد
131
00:04:39,520 –> 00:04:40,560
یا خیر،
132
00:04:40,560 –> 00:04:43,520
اگر در فرهنگ لغت موجود نباشد که
133
00:04:43,520 –> 00:04:44,560
در آن وجود ندارد،
134
00:04:44,560 –> 00:04:46,639
ما در عملگر عضویت از آن استفاده نمی کنیم،
135
00:04:46,639 –> 00:04:48,639
بنابراین این شرط تنها زمانی درست می شود
136
00:04:48,639 –> 00:04:51,680
که v در نمودار وجود نداشته باشد،
137
00:04:51,680 –> 00:04:54,960
سپس
138
00:04:54,960 –> 00:04:57,759
اگر v در نمودار وجود داشته باشد پیامی مانند این چاپ می کنیم، اگر v در نمودار وجود داشته باشد،
139
00:04:57,759 –> 00:04:59,440
کنترل به اینجا می آید
140
00:04:59,440 –> 00:05:01,360
اگر این شرط درست شود،
141
00:05:01,360 –> 00:05:03,919
یعنی v در نمودار وجود ندارد، بنابراین
142
00:05:03,919 –> 00:05:05,440
143
00:05:05,440 –> 00:05:07,360
اگر این شرط نادرست شد، این پیام را چاپ خواهیم کرد،
144
00:05:07,360 –> 00:05:09,120
یعنی v وجود دارد. در
145
00:05:09,120 –> 00:05:12,240
گراف، در غیر این صورت، باید
146
00:05:12,240 –> 00:05:13,199
آن گره
147
00:05:13,199 –> 00:05:16,479
را حذف کنیم تا گره را حذف کنیم، اولین قدم این است که
148
00:05:16,479 –> 00:05:18,560
پس از تأیید وجود v در
149
00:05:18,560 –> 00:05:20,240
نمودار، کاری که باید انجام دهیم، باید
150
00:05:20,240 –> 00:05:20,880
151
00:05:20,880 –> 00:05:24,320
جفت کلید و مقدار گره v را
152
00:05:24,320 –> 00:05:27,199
در این نمودار حذف کنیم. اگر بخواهم c را در
153
00:05:27,199 –> 00:05:30,000
اینجا حذف کنم، باید این جفت کلید و مقدار
154
00:05:30,000 –> 00:05:32,960
را حذف کنم، بنابراین برای حذف این جفت مقدار کلید از
155
00:05:32,960 –> 00:05:34,080
156
00:05:34,080 –> 00:05:37,360
دیکشنری، از روش pop استفاده می کنم،
157
00:05:37,360 –> 00:05:40,400
نام دیکشنری گراف را pop صدا می زنم و در اینجا
158
00:05:40,400 –> 00:05:41,199
به v اشاره می
159
00:05:41,199 –> 00:05:44,720
کنم که حذف است. v از نمودار
160
00:05:44,720 –> 00:05:48,000
آن جفت ارزش کلید را به درستی حذف می کند،
161
00:05:48,000 –> 00:05:50,560
بنابراین این مرحله بعد از این انجام می شود، کاری که
162
00:05:50,560 –> 00:05:51,440
باید انجام
163
00:05:51,440 –> 00:05:54,479
دهیم، باید ارزش همه
164
00:05:54,479 –> 00:05:55,759
کلیدهای دیگر را بررسی کنیم
165
00:05:55,759 –> 00:05:57,680
و در مقادیر باید بررسی
166
00:05:57,680 –> 00:05:59,280
کنیم که آیا گره
167
00:05:59,280 –> 00:06:02,319
v در آن لیست وجود دارد یا خیر، اگر
168
00:06:02,319 –> 00:06:05,520
گره v در لیست در
169
00:06:05,520 –> 00:06:06,080
170
00:06:06,080 –> 00:06:08,880
مقدار کلیدهای دیگر وجود دارد که باید آن را
171
00:06:08,880 –> 00:06:10,240
از لیست حذف کنیم،
172
00:06:10,240 –> 00:06:12,880
بنابراین برای آن ابتدا باید کلید را به عنوان
173
00:06:12,880 –> 00:06:13,600
a
174
00:06:13,600 –> 00:06:16,000
بگیریم، باید مقدار آن را بررسی کنیم و سپس باید
175
00:06:16,000 –> 00:06:17,280
به b
176
00:06:17,280 –> 00:06:19,120
برویم و باید بررسی کنیم. مقدار آن را باید
177
00:06:19,120 –> 00:06:20,960
به d برویم، باید مقدار آن را بررسی کنیم، باید
178
00:06:20,960 –> 00:06:21,680
به e
179
00:06:21,680 –> 00:06:23,600
برویم، باید این مقدار را بررسی کنیم، بنابراین
180
00:06:23,600 –> 00:06:25,520
میخواهیم این عملیات را بارها و
181
00:06:25,520 –> 00:06:27,840
بارها انجام دهیم، به همین دلیل در اینجا از یک حلقه استفاده میکنم
182
00:06:27,840 –> 00:06:29,4