نمودارها در پایتون – تئوری و پیاده سازی

در این درس، نگاهی به یکی از دو الگوریتم مکمل، اساسی و ساده برای پیمایش نمودار خواهیم انداخت – جستجوی اول عمق (DFS). این متداول ترین الگوریتم مورد استفاده در کنار الگوریتم های مرتبط است جستجوی اول عرض (BFS) با توجه به سادگی آنها پس از مرور ایده اصلی مورد استفاده برای DFS، آن را در پایتون پیاده سازی می کنیم روی یک نمایش نمودار – an لیست مجاورت.

جستجوی عمق-اول – نظریه

جستجوی اول عمق (DFS) الگوریتمی است که برای پس و پیش رفتن یا a را پیدا کنید هدف node در یک نمودار یا ساختار داده درختی. اولویت بندی می کند عمق و در امتداد یک شاخه جستجو می کند، تا جایی که می تواند پیش برود – تا پایان آن شاخه. هنگامی که وجود دارد، آن را عقب نشینی می کند به اولین انشعاب ممکن از آن شاخه، و جستجو تا پایان که شاخه، تکرار process.

با توجه به ماهیت الگوریتم، می توانید به راحتی آن را به صورت بازگشتی پیاده سازی کنید – و همیشه می توانید یک الگوریتم بازگشتی را به صورت تکراری نیز پیاده سازی کنید:

شروع کنید node هست root node برای ساختارهای داده درختی، در حالی که با نمودارهای عمومی تر – می تواند هر کدام باشد node.

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

الگوریتم DFS

الگوریتم DFS بسیار ساده است و شامل مراحل زیر است:

1. جریان را علامت گذاری کنید node مانند ملاقات کرد.
2. عبور از همسایه گره هایی که بازدید نمی شوند و به صورت بازگشتی تابع DFS را برای آن فراخوانی کنید node.

الگوریتم یا وقتی هدف متوقف می شود node یافت می شود، یا کل نمودار بوده است عبور کرد (همه گره ها بازدید می شوند).

با علامت گذاری گره ها به عنوان “بازدید شده”، اگر تا به حال با آن مواجه شدیم node دوباره – ما در یک حلقه هستیم! قدرت محاسباتی بی پایان و زمان تلف شده است روی حلقه ها، گم شده در اتر.

شبه کد

با توجه به این مراحل، می توانیم DFS را در شبه کد خلاصه کنیم:

DFS(G, u):
    
    u.visited = true
    for each v in G.adj(u):
        if !v.visited:
            DFS(G, v)
            

ورودی و خروجی پردازش بسته به آن انجام می شود روی هدف از جستجوی نمودار پردازش ورودی ما برای DFS بررسی خواهد شد که آیا جاری node برابر است با هدف node.

با این دیدگاه، شما واقعاً می توانید درک کنید که این الگوریتم چقدر ساده و در عین حال مفید است.

Depth-First Search – پیاده سازی

اولین چیزی که باید قبل از ورود به پیاده سازی خود الگوریتم DFS در نظر بگیریم این است روش پیاده سازی نمودار مانند هر مقاله دیگری از این مجموعه، ما تصمیم گرفتیم آن را با استفاده از یک روش نسبتاً ابتدایی پیاده سازی کنیم Graph کلاس این شامل یک نمایش گراف و چند روش است که برای کار با نمودارها نیاز دارید:

class Graph:
    
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_nodes = range(self.m_num_of_nodes)
		
        
        self.m_directed = directed
		
        
        
        self.m_adj_list = {node: set() for node in self.m_nodes}      
	
    
    def add_edge(self, node1, node2, weight=1):
        self.m_adj_list(node1).add((node2, weight))

        if not self.m_directed:
            self.m_adj_list(node2).add((node1, weight))
    
    
    def print_adj_list(self):
        for key in self.m_adj_list.keys():
            print("node", key, ": ", self.m_adj_list(key))

بیایید به سرعت مرور کنیم که چگونه کار می کند Graph کار کلاسی __init__() متد یک سازنده را تعریف می کند. متشکل از تعدادی گره، مجموعه ای از گره ها، و نمایش نمودار. در این مورد، یک نمودار با یک نشان داده می شود لیست مجاورت – به طور موثر یک فرهنگ لغت پایتون با هر کدام node از نمودار تنظیم شده است که یک کلید باشد. آ مجموعه ای از گره های مجاور به هر یک اختصاص داده شده است node (کلید).

همانطور که از نام آن پیداست، add_edge() روش برای افزودن یال به نمایش گراف استفاده می شود. هر یال مانند هر لیست مجاورت معمولی نشان داده می شود. مثلا لبه 1-2 با افزودن نمایش داده می شود 2 به عنوان مجاور node از node 1 در لیست مجاورت علاوه بر این، پیاده‌سازی ما به شما امکان می‌دهد تا a وزن به هر لبه

در نهایت، ما روشی را ایجاد کرده ایم که نمایش نمودار را چاپ می کند – print_adj_list().

اکنون می توانیم الگوریتم DFS را در آن پیاده سازی کنیم Graph کلاس اجرای Depth-First Search معمولاً انجام می شود بازگشتی در کد با توجه به اینکه یک جفت چقدر طبیعی است، اما می توان آن را به راحتی به صورت غیر بازگشتی نیز پیاده سازی کرد. ما از روش بازگشتی استفاده خواهیم کرد:

def dfs(self, start, target, path = (), visited = set()):
    path.append(start)
    visited.add(start)
    if start == target:
        return path
    for (neighbour, weight) in self.m_adj_list(start):
        if neighbour not in visited:
            result = self.dfs(neighbour, target, path, visited)
            if result is not None:
                return result
    path.pop()
    return None    

شروع را اضافه کردیم node به ابتدای مسیر پیمایش ما و آن را به عنوان علامت گذاری کردیم ملاقات کرد با اضافه کردن آن به مجموعه ای از visited گره ها سپس، شروع را طی کردیم nodeهمسایگان که نیستند قبلاً بازدید کرده و تابع را به صورت بازگشتی برای هر یک از آنها فراخوانی کرده است. تماس های بازگشتی منجر به رفتن به عمق یک “شاخه” می شوند.

سپس یک مرجع به نتیجه را ذخیره کردیم. در حالتی که تابع برمی گردد None، این بدان معنی است که هدف node در این شاخه یافت نشد و باید دیگری را امتحان کنیم. اگر تماس بازگشتی، در واقع، برنگردد None، یعنی ما هدف خود را پیدا کرده ایم node و در نتیجه مسیر پیمایش را برمی گردانیم.

در پایان، اگر ما خود را خارج از for حلقه، به این معنی است که همه شاخه های همسایه جریان node بازدید شده است و هیچ کدام به هدف ما منتهی نمی شود node. بنابراین، جریان را حذف می کنیم node از مسیر و بازگشت None در نتیجه.

اجرای DFS

بیایید روش عملکرد کد را از طریق یک مثال نشان دهیم. همانطور که قبلاً بیان کردیم، استفاده خواهیم کرد Graph کلاس برای نشان دادن نمودار در داخل، یک نمودار را به عنوان یک لیست مجاورت نشان می دهد. در اینجا نموداری است که در مثال زیر از آن استفاده خواهیم کرد:

ما به دنبال راهی از node 0 به node 3، اگر وجود داشته باشد، مسیر در مجموعه ای از گره های بازدید شده ذخیره می شود که نامیده می شود traversal_path بنابراین می توانیم آن را برای چاپ بازسازی کنیم.

اولین کاری که باید انجام دهیم این است که یک نمونه از آن ایجاد کنیم Graph کلاس نمودار مثال ما این است بدون جهت و دارای 5 گره است، بنابراین ما نمایش آن را به روش زیر ایجاد می کنیم:

graph = Graph(5, directed=False)

این نمونه از را ایجاد می کند Graph نشان دهنده گراف بدون جهت با 5 گره. در مرحله بعد، ما باید تمام یال های نمودار مثال را به نمایش گراف خود اضافه کنیم:

graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

اکنون، ما نمایش کامل نمودار مثال را ایجاد کرده ایم. بیایید نگاهی به روش عملکرد آن بیندازیم Graph کلاس به صورت داخلی نمودار مثال ما را ذخیره می کند:

graph.print_adj_list()

که خروجی زیر را دارد:

node 0 :  {(1, 1), (2, 1)}
node 1 :  {(0, 1), (3, 1)}
node 2 :  {(0, 1), (3, 1)}
node 3 :  {(1, 1), (4, 1), (2, 1)}
node 4 :  {(3, 1)}

این ساختار فرهنگ لغت مورد استفاده برای نمایش لیست مجاورت را نشان می دهد. این کاملاً مطابق با اجرای فهرست مجاورت ارائه شده در درس مربوط به نمایش گراف در پایتون است.

در نهایت، ما می توانیم مسیری را پیدا کنیم node 0 به node 3:

traversal_path = ()
traversal_path = graph.dfs(0, 3)
print(traversal_path)

این مسیر پیدا شده را خروجی می دهد:

(0, 1, 3)

اکنون مفید خواهد بود که به مراحلی که الگوریتم ما طی کرده است نگاهی بیندازیم:

• اضافه کردن node 0 به مسیر پیمایش بروید و آن را به عنوان بازدید شده علامت بزنید. بررسی کن اگر node 0 برابر با هدف است node 3، از آنجایی که نیست، ادامه دهید و از همسایگان خود عبور کنید (1 و 2).
• همسایه است 1 ملاقات کرد؟ – خیر. سپس، الگوریتم تابع را به صورت بازگشتی برای آن فراخوانی می کند node.
  • تماس بازگشتی برای node 1: اضافه کردن node 1 به مسیر پیمایش بروید و آن را به عنوان بازدید شده علامت بزنید. است 1 برابر با هدف ما node 3? – نه، ادامه دهید و از همسایگان خود عبور کنید (0 و 3).
  • همسایه است 0 ملاقات کرد؟ – بله ، حرکت کنید روی به بعدی
  • همسایه است 3 ملاقات کرد؟ – نه، تابع را به صورت بازگشتی برای این کار فراخوانی کنید node.
    • تماس بازگشتی برای node 3: اضافه کردن node 3 به مسیر پیمایش بروید و آن را به عنوان بازدید شده علامت بزنید. است 3 برابر با هدف ما node 3? – بله ، هدف node پیدا شد، مسیر پیمایش را برگردانید.

الگوریتم متوقف می شود و برنامه ما مسیر پیمایش حاصل را از آن چاپ می کند node 0 به node 3:

(0, 1, 3)

پس از جستجو، گره های علامت گذاری شده روی نمودار نشان دهنده مسیری است که ما برای رسیدن به هدف طی کردیم node:

در صورتی که هیچ مسیری بین شروع و هدف وجود نداشته باشد node، مسیر پیمایش خواهد بود خالی.

به عنوان مثال در این نمودار، اگر قرار بود DFS را از آن شروع کنیم node 0 به node 4، چنین مسیری وجود نخواهد داشت زیرا راهی برای رسیدن به هدف ندارد node.