در این قسمت تیم کدگیت را با آموزش گراف در پایتون همراهی کنید. پس از اینکه گراف و انواع آن را معرفی کردیم به پیاده سازی گراف غیر جهت دار در پایتون می پردازیم. پیش از ادامه این جلسه، پیشنهاد می‌کنیم پیش‌نیازهای زیر را حتماً مطالعه نمایید:
گراف چیست؟
به مجموعه‌ای از گره‌ها که با یال‌ها به هم متصل شدهاند را گراف می‌گویند. تصویر زیر یک نمونه گراف است:
در گراف بالا یال‌ها(edge) جهت ندارد پس گراف ما غیر جهت دار است. گراف زیر یک گراف جهت‌دار است:
در این آموزش به پیاده‌سازی گراف غیر جهت‌دار می‌پردازیم. برای مطالعه پیاده سازی گراف جهت دار به لینک مراجعه نمایید.
ذخیره‌سازی گراف در پایتون
گراف زیر را در نظر بگیرید:
نحوه ذخیره سازی این گراف در پایتون به صورت زیر می‌باشد:
graph = {0: [1, 4],
1: [0, 4,3,2],
2: [1,3],
3: [1,2,4],
4: [0,1,3]}
همانطور که در کد بالا مشخص است ما از ساختار داده دیکشنری استفاده می‌کنیم. مقدار کلید (key) دیکشنری، گره‌های گراف بوده و به ازای هر کلید، لیستی از گره‌های متصل به آن وجود دارد. گره صفر را در نظر بگیرید، گره‌های متصل به آن 1 و 4 هستند پس متغیر graph در کد بالا یک دیکشنری با شماره 0 دارد که شامل لیستی از اعداد 1 و 4 می‌باشد.
گراف در پایتون
برای پیاده‌سازی گراف یک کلاس به نام UnDirectedGraph ایجاد می‌کنیم:
class UnDirectedGraph:
حال نوبت به پیاده‌سازی متد init است:
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
self.E = 0
graph و E ویژگی‌های کلاس UnDirectedGraph هستند. graph که دیکشنری بوده (که در قسمت قبل توضیح دادیم) و E نیز تعداد یال‌های گراف می‌باشد. البته این نکته هم اشاره کنیم که برای استفاده از defaultdict باید آن را فراخوانی کنید:
from collections import defaultdict
addEdge متد دیگری است که می‌خواهیم آن را پیاده‌سازی کنیم. این متد(با دریافت دو گره متصل) یک یال را به گراف اضافه می‌کند. پیاده سازی این متد به صورت زیر است:
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
در شرط if اول بررسی می‌کنیم آیا قبلا یال ورودی را در گراف اضافه کرده‌ایم یا خیر. در شرط دوم بررسی می‌کنیم آیا یال ورودی، حلقه است یا خیر (حلقه یالی است که یک گره را به خودش متصل می‌کند). در پایان با صدا زدن متد append دو گره را به هم متصل می‌کنیم. باید توجه کرد که در گراف غیر جهت‌دار در صورتی که u به v متصل باشند v نیز به u متصل است. در پایان یک واحد به تعداد یال‌ها (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 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()
if __name__ == '__main__':
g = UnDirectedGraph()
g.addEdge(0, 1)
g.addEdge(0, 4)
g.addEdge(1, 0)
g.addEdge(1, 4)
g.addEdge(1, 3)
g.addEdge(1, 2)
g.addEdge(2, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
g.addEdge(3, 2)
g.addEdge(3, 4)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(4, 3)
g.printGraph()
در main برنامه یک گراف ایجاد کرده و 7 یال تصویر قبل را به آن اضافه کردیم در پایان گراف را چاپ کردیم. خروجی کد بالا به صورت زیر می‌باشد:
0 : 1 4
1 : 0 4 3 2
4 : 0 1 3
3 : 1 2 4
2 : 1 3
