الگوریتم جستجوی عمق اول - ویکی‌پدیا، دانشنامهٔ آزاد

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

ترتیبی که راس‌ها پیمایش می‌شوند
رده	الگوریتم جستجو
ساختمان داده	گراف (ساختار داده)
کارایی بدترین حالت	${\displaystyle O(|V|+|E|)}$ for explicit graphs traversed without repetition, ${\displaystyle O(b^{d})}$ for implicit graphs with branching factor b searched to depth d
پیچیدگی فضایی	${\displaystyle O(|V|)}$ if entire graph is traversed without repetition, O(longest path length searched)=${\displaystyle O(bd)}$for implicit graphs without elimination of duplicate nodes

در نظریهٔ گراف، جستجوی عمق اول (به انگلیسی: Depth-first Search، به‌اختصار DFS) یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک گراف به کار می‌رود. روش جستجوی عمق اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی رأس‌های عمیق‌تر در گراف تا زمانی که امکان دارد» است.

الگوریتم از یک راس دلخواه (ریشه در درخت‌های ریشه‌دار) شروع می‌کند و در هر مرحله همسایه‌های رأس جاری را از طریق یال‌های خروجی رأس جاری به ترتیب بررسی کرده و به محض روبه‌رو شدن با همسایه‌ای که قبلاً دیده نشده باشد، به صورت بازگشتی برای آن رأس به عنوان رأس جاری اجرا می‌شود. در صورتی که همهٔ همسایه‌ها قبلاً دیده شده باشند، الگوریتم عقب‌گرد می‌کند و اجرای الگوریتم برای رأسی که از آن به رأس جاری رسیده‌ایم، ادامه می‌یابد. به عبارتی الگوریتم تا آنجا که ممکن است، به عمق بیشتر می‌رود و در مواجهه با بن‌بست عقب‌گرد می‌کند. این فرایند تا زمانی که همهٔ رأس‌های قابل دستیابی از ریشه دیده شوند ادامه می‌یابد.

همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گراف‌اند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است، جستجوی عمق اول مفید است. در هر گام، الگوریتم در صورت امکان به اولین همسایهٔ دیده نشده یک رأس در گراف جستجو می‌رود تا به رأسی برسد که همهٔ همسایگانش دیده شده‌اند که در حالت اخیر، الگوریتم به اولین رأسی بر می‌گردد که همسایهٔ داشته باشد که هنوز دیده نشده باشد. این روند تا جایی ادامه می‌یابد که رأس هدف پیدا شود یا همهٔ مولفهٔ همبندی گراف پیمایش شود. البته پیاده‌سازی هوشمندانهٔ الگوریتم با انتخاب ترتیب مناسب برای بررسی همسایه‌های دیده نشدهٔ رأس جاری به صورتی که ابتدا الگوریتم به بررسی همسایه‌ای بپردازد که به صورت موضعی و با انتخابی حریصانه به رأس هدف نزدیک‌تر است، امکان‌پذیر خواهد بود که در کاهش زمان اجرا مؤثر است.

برای اجرای الگوریتم، از یک پشته استفاده می‌شود. بدین ترتیب که هر بار با ورود به یک رأس دیده نشده، آن رأس را در پشته قرار می‌دهیم و هنگام عقب‌گرد رأس را از پشته حذف می‌کنیم؛ بنابراین در تمام طول الگوریتم اولین عنصر پشته رأس در حال بررسی است.

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

پیمایش با انتخاب رأس ${\displaystyle r}$ به عنوان ریشه آغاز می‌شود. در هر گام که در راس ${\displaystyle v}$ قرار داشته باشیم، ابتدا آن راس به عنوان یک رأس دیده شده برچسب می‌خورد. رأس دلخواه دیده نشده ${\displaystyle w}$ از همسایگان ${\displaystyle v}$ انتخاب شده و الگوریتم به صورت بازگشتی از ${\displaystyle v}$ فرایند خود را ادامه می‌دهد. اگر در رأسی مانند ${\displaystyle v'}$ قرار گرفتیم که همهٔ همسایگانش دیده شده‌اند، اجرای الگوریتم را برای آن رأس خاتمه می‌دهیم. روند الگوریتم تا مادامی که همهٔ همسایگان ${\displaystyle r}$ دیده نشده باشند ادامه می‌یابد.

ورودی گراف ${\displaystyle G}$ و راس  ${\displaystyle v}$ از گراف  ${\displaystyle G}$ خروجی پیمایشی از گراف ${\displaystyle G}$ شامل رأس‌های قابل دسترسی از ${\displaystyle v}$ 

نسخهٔ بازگشتی الگوریتم به این شکل است:

الگوریتم ${\displaystyle DFS(G,v)}$  راس ${\displaystyle v}$ را برچسب بزن.  برای همه راس‌های ${\displaystyle w}$ که از ${\displaystyle v}$  به آن‌ها یال هست :  اگر راس ${\displaystyle w}$ برچسب نخورده بود آنگاه:  DFS(G,w) را اجرا کن. 

و یک نسخهٔ غیر بازگشتی الگوریتم به این قرار است:

الگوریتم ${\displaystyle DFS(G,v)}$  راس ${\displaystyle v}$ را وارد پشته کن و آن را برچسب بزن.  تا زمانی که پشته خالی نیست :  راس ${\displaystyle v}$ را برابر راس برداشته شده ار بالای پشته قرار بده.  برای همه راس‌های ${\displaystyle w}$ که از ${\displaystyle v}$  به آن‌ها یال هست و برچسب نخورده‌اند:  راس ${\displaystyle w}$ را وارد پشته کن و آن را برچسب بزن. 

مشخص است که الگوریتم، هر یال در گراف بدون جهت را دقیقاً دو بار (یک بار به به هنگام بررسی هر یک از دو انتها) و هر یال در گراف جهت‌دار را دقیقاً یک بار پیمایش می‌کند. همچنین هر رأس قابل دسترسی از ریشه دقیقاً یک بار بازدید خواهد شد؛ بنابراین پیچیدگی زمانی جستجوی عمق اول (|O(|V|+|E خواهد بود.

یکی از کاربردهای این الگوریتم تشخیص وجود دور است. در گراف ساده، برای این کار رویهٔ عادی جستجو عمق اول را در پیش می‌گیریم، تنها با این تفاوت که یک لیست نشانه و یک لیست پدر می‌سازیم که در ابتدا برای هر کدام از رئوس به ترتیب مقادیر نادرست (به انگلیسی: False) و اشاره‌گر تهی (به انگلیسی: Null) دارد، زیرا در ابتدای امر هیچ‌کدام از رئوس دیده نشده‌اند و پدر آن‌ها در جنگل فراگیری که قرار است این الگوریتم بسازد، نامشخص است.

سپس در هر مرحله بررسی می‌شود که اگر رأس کنونی v که به وسیله رأس u پیدا شده‌است، قبلاً نشانه‌گذاری شده بود و خود v پدر u نبود، در این صورت یک یال بازگشت (به انگلیسی: Back Edge) پیدا شده‌است که نشان می‌دهد گراف دور دارد. در غیر این صورت رأس v نشانه گذاری شده و پدر آن رأس u می‌شود. در صورتی که تا پایان مراحل اجرا هیچ یال بازگشت‌ای پیدا نشد، یعنی گراف بدون دور است.

در زیر پیاده‌سازی این روش به وسیله زبان پایتون آماده است.

class Graph:     def __init__(self, number_of_nodes):         self.number_of_nodes = number_of_nodes         self.node_neighbours = [[] for i in range(self.number_of_nodes)]      def get_input(self):  # vertex indexes start from zero. (not one)         for i in range(len(self.node_neighbours)):             self.node_neighbours[i].extend(list(map(int, input().split())))  # get and add neighbour(s) of i-th vertex      def dfs(self, node_index, parent_index, mark_lst, parent_lst):         if mark_lst[node_index]:             if parent_index is not None and node_index != parent_lst[parent_index]:                 # indicates there exist a back-edge to a previously seen vertex (node_index) which is not the parent                 return True             return False         mark_lst[node_index], parent_lst[node_index] = True, parent_index         for neighbour_index in self.node_neighbours[node_index]:             if self.dfs(neighbour_index, node_index, mark_lst, parent_lst):                 return True         return False      def find_cycle(self):         mark, parent = [False] * self.number_of_nodes, [None] * self.number_of_nodes         for i in range(self.number_of_nodes):             if not mark[i]:                 if self.dfs(i, None, mark, parent):                     return True         return False 

• پیدا کردن مؤلفه‌های همبندی
• مرتب‌سازی موضعی (Topological Sort)
• پیدا کردن اجزای قویا همبند گراف جهت‌دار
• پیدا کردن مؤلفه‌های دوهمبند یالی و رأسی
• پیدا کردن پل
• الگوریتم انباشتن سیلابی^[۱]
• پیدا کردن دور در گراف^[۲]
• حل کردن معماهایی همچون ماز و آنهایی که نیاز به بررسی همه یا بخش بزرگی از حالات ممکن دارند.
• پیدا کردن گراف دوهمبند

در ویکی‌انبار پرونده‌هایی دربارهٔ الگوریتم جستجوی عمق اول موجود است.

• Open Data Structures - Section 12.3.2 - Depth-First-Search
• Depth-First Explanation and Example
• C++ Boost Graph Library: Depth-First Search
• Depth-First Search Animation (for a directed graph)
• Depth First and Breadth First Search: Explanation and Code
• QuickGraph^{[پیوند مرده]}, depth first search example for .Net
• Depth-first search algorithm illustrated explanation (Java and C++ implementations)
• YAGSBPL – A template-based C++ library for graph search and planning
• توضیح و مثال‌هایی از جستجوی عمق اول
• انیمیشن جستجوی عمق اول برای گراف‌های جهت‌دار
• توضیح و پیاده‌سازی جستجوی عمق اول و جستجوی سطح اول
• Dfs Applet