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

در این آموزش تیم کدگیت را با توضیح جستجوی اول عمق در پایتون همراهی کنید. در ابتدای جلسه جستجوی اول عمق را توضیح، سپس به پیاده‌سازی آن در پایتون خواهیم پرداخت. پیش‌نیاز این آموزش شامل موارد زیر می‌باشد:

• گراف در پایتون
• گراف جهت‌دار در پایتون
• لیست در پایتون
• حلقه While در پایتون
• تابع در پایتون
• حلقه For در پایتون
• شرط if در پایتون

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

در نظریه‌ گراف، جستجوی عمق اول یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار می‌رود.استراتژی جستجوی عمق اول برای پیمایش گراف، همانطور که از نامش پیداست “جستجوی عمیق‌تر در گراف تا زمانی که امکان دارد” است.

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

پیاده سازی جستجوی اول عمق در پایتون

در آموزش گذشته پیاده سازی گراف را انجام داده‌ایم و از همان پیاده‌سازی برای این آموزش استفاده می‌شود. کد گرافی که در جلسه گذشته پیاده سازی کردیم به صورت زیر است:

from collections import defaultdict 
class UnDirectedGraph: 
     # Constructor 
    def __init__(self): 
  
        # default dictionary to store graph 
        self.graph = defaultdict(list)
        self.E = 0 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        if v in self.graph[u]:
            return 
        if u == v:
            self.graph[u].append(v)
            return
        
        self.graph[u].append(v)
        self.graph[v].append(u)
        self.E+=1 
    def V(self):
        return len(self.graph)
    def Edge(self):
        return self.E
    
    def printGraph(self):
        for i in self.graph: 
            print(i,':',end=' ')
            for j in self.graph[i]:
                print(j, end= ' ')
            print()

برای پیاده سازی جستجوی اول عمق در پایتون از ساختار داده Set استفاده می‌کنیم. یک متد با نام DFS ایجاد می‌کنیم. ورودی این متد گره ریشه و مجموعه Set می‌باشد. در صورتی که گره‌ای را بررسی کردیم مقدار آن در set ذخیره می‌شود. کد این قسمت به صورت زیر است:

def DFS(self, s, visited = set()):

حال نوبت به پیاده سازی الگوریتم می‌رسد. ابتدا گره ورودی متد DFS را وارد متغیر Visited می‌کنیم:

        visited.add(s)
        print(s, end=' ')

در پایان الگوریتم تمام گره‌های متصل به s را به صورت بازگشتی صدا زده و متد DFS را بر روی آن‌ها اجرا می‌کنیم:

        for neighbour in self.graph[s]:
            if neighbour not in visited:
                self.DFS(neighbour, visited)   

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

برای تست کدهای بالا، main زیر را اجرا کنید:

if __name__ == '__main__':
    g = UnDirectedGraph()
    g.addEdge(0, 1) 
    g.addEdge(0, 4) 
    g.addEdge(1, 4) 
    g.addEdge(1, 3) 
    g.addEdge(1, 2) 
    g.addEdge(2, 3) 
    g.addEdge(3, 4) 
    print('print Graph:')
    g.printGraph()
    print('DFS',end=' ')
    g.DFS(2)

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

خروجی برنامه نیز به صورت زیر است:

print Graph:

0 : 1 4

1 : 0 4 3 2

4 : 0 1 3

3 : 1 2 4

2 : 1 3

DFS 2 1 0 4 3

ویدئو آموزش