ویرگول
ورودثبت نام
Elias Rouhani
Elias Rouhaniنویسنده های خوب کسانی هستند که به خوبی رونویسی می‌کنند
Elias Rouhani
Elias Rouhani
خواندن ۲ دقیقه·۶ سال پیش

الگوریتم جستجو در عمق یا DFS

امروز می خواهیم درباره الگوریتمی به نام جستجوی عمیق(Depth-first search) حرف بزنیم، معمولا درباره این الگورتیم ها اگه اشتباه نکنم در دانشگاه بحثی نمی شود ولی خالی از لطف نیستند، الگوریتم های بسیار مفیدی هستند.

در این الگوریتم همانطور که از نام اش پیدا است در یک شاخه جستجو انجام می شود به این صورت که پیمایش از همه گروه ها نمودار است. این الگوریتم یک الگوریتم یک الگوریتم بازگشتی است که در تمامی شاخه ها جستجو می کند.

استاندارد اجرای الگوریتم DFS به دو صورت روبه رو انجام می شود: دیده شده ها و دیده نشده ها

این الگوریتم به شرح زیر کار می کند که:

۱-اول از همه با قرار دادن هر راس نمودار در بالای پشته(stack) شروع می کند

۲-بالاترین نقطه از نمودار را بردارید و ان را در لیست دیده شده قرار دهید

۳-یک لیست گروه مجاور این راس ایجاد کنید و مواردی که در لیست بازدید نشده اند را در ابتدای پشته اضافه کنید.

۴-و در اخر هم مراحل دو و سه را انجام دهید.

برای مثال:

بیاید ببنیم این الگوریتم چگونه کار می کند ما از یک نمودار بدون جهت با ۵ راس یا همانNODE استفاده می کنیم.

Visited دیده شده ها

Stack پشته


ما از بالاترین راس یا همان نود شروع می کنیم که همان صفر می شود، این الگوریتم با قرار دادن تمامی نودها در دیده شده و نودها مجاور در پشته شروع می شود. پس اگر دقت کنید همسایه صفر اعداد سه دو یک است که در پشته قرار می گیرد.

سپس از بالاترین نقطه پشته که می شود همون یک بازدید می کنیم، همانطور که می بینید چون قبلا از صفر بازید شده است، عدد دو را بازدید می کنیم، نکته که هست چون عدد یک بازدید شده هست باید به حافظه بازیدشده جایگزاری شود. پس هر وقت می گویم بازید شده است باید در خانه خود قرار بگیرد.

همانطور که می ببیند نود یا راس ۲ یک همسایه دارد پس در نتیجه مثل قبل به بازدید شده اضافه می کنیم.

همانطوری که می ببنید عدد سه دیگر همسایه ندارد و در اینجاست که جستجوی ما به پایان می رسد.

همچنین اگر خواستید می تونید به برنامه DFS هم سربزنید

الگوریتم جستجو در عمق با پایتون

def DFS(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph[start] - visited: DFS(graph, next, visited) return visited graph = {'0': set(['1', '2']), '1': set(['0', '3', '4']), '2': set(['0']), '3': set(['1']), '4': set(['2', '3'])} DFS(graph, '0')
الگوریتمدرخت
۵
۰
Elias Rouhani
Elias Rouhani
نویسنده های خوب کسانی هستند که به خوبی رونویسی می‌کنند
شاید از این پست‌ها خوشتان بیاید