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

ترتیب پیمایش رئوس در جستجوی عمق اول
در نظریه گراف، جستجوی عمق اول یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار می‌رود.
استراتژی جستجوی عمق اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی عمیق‌تر در گراف تا زمانی که امکان دارد» است.
چگونه کار می‌کند؟
الگوریتم از ریشه شروع می‌کند (در گراف‌ها یا درخت‌های بدون ریشه راس دلخواهی به عنوان ریشه انتخاب می‌شود) و در هر مرحله همسایه‌های راس جاری را از طریق یال‌های خروجی راس جاری به ترتیب بررسی کرده و به محض روبه‌رو شدن با همسایه‌ای که قبلا دیده نشده باشد، به صورت بازگشتی برای آن راس به عنوان راس جاری اجرا می‌شود. در صورتی که همه همسایه‌ها قبلا دیده شده باشند، الگوریتم عقب‌گرد می‌کند و اجرای الگوریتم برای راسی که از آن به راس جاری رسیده‌ایم، ادامه می‌یابد. به عبارتی الگوریتم تا آنجا که ممکن است، به عمق بیشتر و بیشتر می‌رود و در مواجهه با بن‌بست عقب‌گرد می‌کند. این فرایند تا زمانی که همه راس‌های قابل دستیابی از ریشه دیده شوند ادامه می‌یابد.
همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گراف‌اند و حل مسئله مستلزم یافتن راس هدف با خصوصیات مشخصی است، جستجوی عمق اول به صورت غیرخلاق عمل می‌کند. بدین‌ترتیب که هر دفعه الگوریتم به اولین همسایه یک راس در گراف جستجو و در نتیجه هر دفعه به عمق بیشتر و بیشتر در گراف می‌رود تا به راسی برسد که همه همسایگانش دیده شده‌اند که در حالت اخیر، الگوریتم به اولین راسی بر می‌گردد که همسایه داشته باشد که هنوز دیده نشده باشد. این روند تا جایی ادامه می‌یابد که راس هدف پیدا شود یا احتمالا همه گراف پیمایش شود. البته پیاده‌سازی هوشمندانه الگوریتم با انتخاب ترتیب مناسب برای بررسی همسایه‌های دیده نشده راس جاری به صورتی که ابتدا الگوریتم به بررسی همسایه‌ای بپردازد که به صورت موضعی و با انتخابی حریصانه به راس هدف نزدیک‌تر است، امکان‌پذیر خواهد بود که معمولا در کاهش زمان اجرا موثر است.
از دیدگاه عملی، برای اجرای الگوریتم، از یک پشته استفاده می‌شود. بدین ترتیب که هر بار با ورود به یک راس دیده نشده، آن راس را در پشته قرار می‌دهیم و هنگام عقب‌گرد راس را از پشته حذف می‌کنیم؛ بنابراین در تمام طول الگوریتم اولین عنصر پشته راس در حال بررسی است. جزئیات پیاده‌سازی در ادامه خواهد آمد.
وقتی در گراف‌های بزرگی جستجو می‌کنیم که امکان ذخیره کامل آن‌ها به علت محدودیت حافظه وجود ندارد، در صورتی که طول مسیر پیمایش شده توسط الگوریتم که از ریشه شروع شده، خیلی بزرگ شود، الگوریتم با مشکل مواجه خواهد شد. در واقع این راه‌حل ساده که «رئوسی را که تا به حال دیده‌ایم ذخیره کنیم» همیشه کار نمی‌کند. چرا که ممکن است حافظه کافی برای این کار نداشته باشیم. البته این مشکل با محدود کردن عمق جستجو در هر بار اجرای الگوریتم حل می‌شود که در نهایت به الگوریتم جستجوی عمق اول عمیق‌کننده تکراری خواهد انجامید.
الگوریتم
پیمایش با انتخاب راس به عنوان ریشه آغاز می‌شود. به عنوان یک راس دیده شده برچسب می‌خورد. راس دلخواه از همسایگان انتخاب شده و الگوریتم به صورت بازگشتی از به عنوان ریشه ادامه می‌یابد. از این پس در هر مرحله وقتی در راسی مانند قرار گرفتیم که همه همسایگانش دیده شده‌اند، اجرای الگوریتم را برای آن راس خاتمه می‌دهیم. حال اگر بعد از اجرای الگوریتم با ریشه همه همسایگان برچسب خورده باشند، الگوریتم پایان می‌یابد. در غیر این صورت راس دلخواه از همسایگان را که هنوز برچسب نخورده انتخاب می‌کنیم و جستجو را به صورت بازگشتی از به عنوان ریشه ادامه می‌دهیم. این روند تامادامی که همه همسایگان برچسب نخورده‌اند ادامه می‌یابد.
البته پیمایش گراف برای تامین هدفی صورت می‌گیرد. بر این اساس برای انعطاف‌پذیر ساختن الگوریتم در قبال کاربردهای مختلف، دو نوع عملیات preWORK و postWORK را به همراه بازدید از هر راس یا یال انجام می‌دهیم، که preWORK در زمان برچسب خوردن راس در حال بازدید، و postWORK بعد از بررسی هر یال خروجی از راس در حال بازدید انجام خواهد شد. هر دوی این عملیات وابسته به هدف استفاده از الگوریتم، مشخص خواهند شد.
الگوریتم بازگشتی جستجوی اول عمق به صورت زیر است. آرایه یک بعدی Visited تعیین می‌کند آیا راسی قبلا ملاقات شده‌است یا خیر. اگر راس vi ملاقات شود Visitedi برابر با یک می‌شود.
1 DFS (int v)
2 {
3 int w
4 Visitedv:=1
5 For (each vertex w adjacent to v)
6 If (not visitedw) then
7 DFS(w)
8 End if
9 End For
10
ترتیب ملاقات رئوس را DFN می‌نامند.
پیاده‌سازی
یک نسخه بازگشتی الگوریتم به این قرار است:
1 Algorithm DFS(G,v)
2 Input : G=(V,E), v(a vetex of G)
3 Output : depends on the application
4 begin
5 mark v
6 perform preWORK on v
7 for all edge (v,w) do
8 if w is unmarked then
9 DFS(G,w)
10 perform postWORK on (v,w)
11 end
و یک نسخه غیر بازگشتی الگوریتم به این قرار است:
1 Algorithm DFS(G,v)
2 Input : G=(V,E), v(a vertex of G)
3 Output : depends on the application
4 begin
5 mark v
6 perform preWORK on v
7 Edge = v.First
8 push v and Edge on the top of the stack
9 Parent = v
10 while the stack is not empty do
11 remove Edge from the top of the stack
12 while Edge is not nil do
13 Child = Edge->Vertex
14 if Child is unmarked then
15 mark Child
16 perform preWORK on Child
17 push Edge->Next to the top of the stack
18 Edge = Child.First
19 Parent = Child
20 push Parebtto the top of the stack
21 else
22 perform postWORK on (Parent,Child)
23 Edge = Edge->Next
24 remove Child from the top of the stack
25 if the stack is not empty then
26 let Edge and Parent be at the top of the stack
27 perform postWORK on (Parent,Child)
28 end
که v.First به معنی اولین یال متصل به v و Edge->Vertex به معنی راس انتهای Edge و Edge->Next به معنی یال بعدی متصل به ابتدای Edge است.
پیچیدگی زمانی
مشخص است که الگوریتم، هر یال در گراف بدون جهت را دقیقا دوبار (یک بار به به هنگام بررسی هر یک از دو انتها) و هر یال در گراف جهت‌دار را دقیقا یک بار پیمایش می‌کند. همچنین هر راس قابل دسترسی از ریشه دقیقا یک بار بازدید خواهد شد. پس با فرض همبند بودن گراف و اینکه preWORK و postWORK در (1)O انجام شوند، پیچیدگی زمانی جستجوی عمق اول (|O(|V|+|E خواهد بود
تشخیص وجود دور
یکی از کاربردهای این الگوریتم تشخیص وجود دور است. در گراف ساده، برای این کار رویه عادی جستجو عمق اول را در پیش می‌گیریم، تنها با این تفاوت که یک لیست نشانه و یک لیست پدر می‌سازیم که در ابتدا برای هر کدام از رئوس به ترتیب مقادیر نادرست و اشاره‌گر تهی دارد، زیرا در ابتدای امر هیچ‌کدام از رئوس دیده نشده‌اند و پدر آن‌ها در جنگل فراگیری که قرار است این الگوریتم بسازد، نامشخص است.
سپس در هر مرحله بررسی می‌شود که اگر راس کنونی v که به وسیله راس u پیدا شده است، قبلا نشانه‌گذاری شده بود و خود v پدر u نبود، در این صورت یک یال بازگشت پیدا شده‌است که نشان می‌دهد گراف دور دارد. در غیر این صورت راس v نشانه گذاری شده و پدر آن راس u می‌شود. در صورتی که تا پایان مراحل اجرا هیچ یال بازگشت‌ای پیدا نشد، یعنی گراف بدون دور است.
در زیر پیاده‌سازی این روش به وسیله زبان پایتون آماده است.
class Graph:
def (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_neighboursi.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_lstnode_index:
if parent_index is not None and node_index != parent_lstparent_index:
# indicates there exist a back-edge to a previously seen vertex (node_index) which is not the parent
return True
return False
mark_lstnode_index, parent_lstnode_index = True, parent_index
for neighbour_index in self.node_neighboursnode_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 marki:
if self.dfs(i, None, mark, parent):
return True
return False
مراحل پیدا کردن دور در گراف ساده به وسیله الگوریتم جستجوی عمق اول
کاربردها
پیدا کردن مولفه‌های همبندی
مرتب‌سازی موضعی (Topological Sort)
پیدا کردن اجزای قویا همبند گراف جهت‌دار
پیدا کردن مولفه‌های دوهمبند یالی و راسی
پیدا کردن پل
الگوریتم انباشتن سیلابی
پیدا کردن دور در گراف
حل کردن معماهایی همچون ماز و آنهایی که نیاز به بررسی همه یا بخش بزرگی از حالات ممکن دارند.
پیدا کردن گراف دوهمبند
, depth first search example for .Net