گراف جهت‌دار در پایتون

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

• List در پایتون
• توابع در پایتون
• حلقه For در پایتون
• آشنایی با شی‌گرایی در پایتون
• دیکشنری در پایتون
• If در پایتون

گراف جهت دار

به مجموعه‌ای از گره‌ها که با یال‌ها به هم متصل شده‌‌اند را گراف می‌گویند. اگر یال‌های گراف جهتی داشته باشند آن را گراف جهت‌دار می‌گویند. به عنوان مثال تصویر زیر شامل 8 گره و 9 یال، یک گراف جهت دار می‌باشد.

ذخیره‌سازی گراف در پایتون

برای نمایش گراف تصویر بالا در زبان پایتون ما به صورت زیر عمل می‌کنیم:

    graph = {7: [11, 8],
             3: [8, 10],
             5: [11],
             11: [2,9,10],
          8: [9]}

همانطور که در کد بالا مشخص است ما از ساختار داده دیکشنری استفاده می‌کنیم. مقدار کلید (key) دیکشنری گره‌های گراف بوده و به ازای هر کلید، لیستی از گره‌های متصل به آن وجود دارد. برای مثال گره شماره 7 در نظر بگیرید، گره‌های متصل به این گره، 11 و 8 می‌باشند. به همین دلیل متغیر graph در کد بالا یک دیکشنری با شماره 7 دارد که شامل لیستی از اعداد 11 و 8 می‌باشد.

گراف جهت‌دار در پایتون

برای پیاده سازی گراف جهت دار یک کلاس با نام DirectedGraph ایجاد می‌کنیم.

class DirectedGraph: 

متد __init__ کلاس بالا به صورت زیر است:

    def __init__(self): 
  
        # default dictionary to store graph 
        self.graph = defaultdict(list)
        self.E = 0 

graph و E ویژگی‌های کلاس DirectedGraph هستند. graph که دیکشنری بوده(که در قسمت قبل توضیح دادیم) و E نیز تعداد یال‌های گراف می‌باشد. البته این نکته هم اشاره کنیم که برای استفاده از  defaultdict باید آن را فراخوانی کنید:

from collections import defaultdict

حال نوبت به پیاده سازی متد addEdge می‌باشد. این متد(با دریافت دو گره متصل از u به v) یک یال را به گراف اضافه می‌کند. پیاده سازی این متد به صورت زیر است:

    def addEdge(self,u,v): 
        self.graph[u].append(v)
        if v not in self.graph.keys():
            self.graph[v]
        self.E+=1 

با کمک تابع append دو گره u و v را به هم متصل کردیم. شرط if به این دلیل قرار داده شده است که در گراف جهت‌دار ممکن است گره‌ای به عنوان مبدا نباشد(مانند گره‌های 2 و 9 و 10 در تصویر قبل) پس در متغیر graph اضافه نمی‌گردد با شرط if ما در گراف یک لیست خالی از گره‌های توضیح داده شده ایجاد می‌کنیم. همچنین در خط پایانی یک واحد به متغیر E که نشان‌دهنده یال بود، اضافه کردیم.

متد printGraph برای نشان دادن گراف به کار می‌روند پیاده سازی این متد به صورت زیر است:

    def printGraph(self):
        for i in self.graph: 
            print(i,':',end=' ')
            for j in self.graph[i]:
                print(j, end= ' ')
            print()

 در کد بالا به ازای هر گره، گره‌های متصل به آن را دریافت و آن را چاپ کردیم. برای دریافت تعداد گره‌ها و تعداد یال‌ها از متدهای V و Edge استفاده می‌کنیم:

    def V(self):
        return len(self.graph)
    def Edge(self):
        return self.E

تست برنامه

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

from collections import defaultdict 
class DirectedGraph: 
  
    # 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): 
        self.graph[u].append(v)
        if v not in self.graph.keys():
            self.graph[v]
        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()                  
if __name__ == '__main__':
    g = DirectedGraph() 
    g.addEdge(7, 11) 
    g.addEdge(7, 8) 
    g.addEdge(5, 11) 
    g.addEdge(3, 8)
    g.addEdge(3, 10)
    g.addEdge(11, 2)
    g.addEdge(11, 9)
    g.addEdge(11, 10) 
    g.addEdge(8, 9) 
    g.printGraph()

در main برنامه یک گراف ایجاد کرده و 9 یال تصویر قبل را به آن اضافه کردیم در پایان گراف را چاپ کردیم. خروجی کد بالا به صورت زیر می‌باشد:

7 : 11 8
11 : 2 9 10
8 : 9
5 : 11
3 : 8 10
10 :
2 :
9 :

ویدئو آموزش