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

در این درس به تئوری پشت الگوریتم و پیاده سازی پایتون می پردازیم جستجو و پیمایش عرض اول. اول، ما تمرکز می کنیم روی node جستجو کردن، قبل از پرداختن به پیمایش نمودار با استفاده از الگوریتم BFS، به عنوان دو وظیفه اصلی که می توانید آن را برای آن به کار ببرید.

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

جستجوی اول عرض (BFS) نمودار را به طور سیستماتیک طی می کند، سطح به سطح، تشکیل یک درخت BFS در طول مسیر.

اگر جستجوی خود را از node v ( root node از نمودار یا ساختار داده درختی ما)، الگوریتم BFS ابتدا از همه موارد بازدید می کند همسایه ها از node v (این گره های کودک هستند، روی مرحله اول) به ترتیبی که در لیست مجاورت آمده است. بعد، گره های فرزند آن همسایگان را می گیرد (سطح دو) در نظر گرفته شود و غیره روی.

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

جستجوی عرض-اول می توان برای حل بسیاری از مسائل از جمله یافتن کوتاه ترین مسیر بین دو گره، تعیین سطوح هر یک استفاده کرد. nodeو حتی حل بازی های پازل و پیچ و خم ها.

در حالی که این الگوریتم کارآمدترین الگوریتم برای حل پیچ و خم ها و معماهای بزرگ نیست – و الگوریتم هایی مانند الگوریتم Dijkstra و A* از آن برتری دارد – همچنان نقش مهمی در این دسته بازی می کند و بسته به آن روی مشکل در دست – DFS و BFS می توانند از پسرعموهای اکتشافی خود بهتر عمل کنند.

جستجوی عرض-اول – الگوریتم

هنگام پیاده سازی BFS، ما معمولا از a استفاده می کنیم FIFO ساختاری مانند a Queue برای ذخیره گره هایی که در مرحله بعدی بازدید خواهند شد.

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

برای جمع بندی منطق، مراحل الگوریتم BFS به شکل زیر است:

1. اضافه کردن root/شروع node به Queue.
2. برای هر node، تنظیم کنید که آنها یک والد تعریف شده نداشته باشند node.
3. تا Queue خالی است:
   • را استخراج کنید node از ابتدای Queue.
   • پردازش خروجی را انجام دهید.
   • برای هر همسایه جریان node که نمی کند یک والد تعریف شده داشته باشید (بازدید نشده است)، آن را به آن اضافه کنید Queueو جریان را تنظیم کنید node به عنوان والدین آنها

اجرای جستجوی Breadth-First – جستجوی گره هدف

بیایید ابتدا شروع کنیم جستجو کردن – و برای یک هدف جستجو کنید node. علاوه بر هدف node، ما به یک شروع نیاز خواهیم داشت node همچنین. خروجی مورد انتظار a است مسیر که از همان ابتدا ما را هدایت می کند node به هدف node.

با در نظر گرفتن آنها و در نظر گرفتن مراحل الگوریتم، می توانیم آن را پیاده سازی کنیم. ما a را تعریف می کنیم Graph کلاس برای “پوشش” اجرای جستجوی BFS.

Graph شامل یک نمایش گراف – در این مورد یک ماتریس مجاورت، و همه روش هایی است که ممکن است هنگام کار با نمودارها به آن نیاز داشته باشید. هم جستجوی BFS و هم پیمایش BFS را به عنوان متدهای آن کلاس پیاده سازی می کنیم:

from queue import Queue

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))

پس از اجرای الف لفاف کلاس، می توانیم جستجوی BFS را به عنوان یکی از روش های آن پیاده سازی کنیم:

def bfs(self, start_node, target_node):
    
    visited = set()
    queue = Queue()

    
    queue.put(start_node)
    visited.add(start_node)
    
    
    parent = dict()
    parent(start_node) = None

    
    path_found = False
    while not queue.empty():
        current_node = queue.get()
        if current_node == target_node:
            path_found = True
            break

        for (next_node, weight) in self.m_adj_list(current_node):
            if next_node not in visited:
                queue.put(next_node)
                parent(next_node) = current_node
                visited.add(next_node)
                
    
    path = ()
    if path_found:
        path.append(target_node)
        while parent(target_node) is not None:
            path.append(parent(target_node)) 
            target_node = parent(target_node)
        path.reverse()
    return path 

وقتی مسیر را بازسازی می کنیم (اگر پیدا شد)، از هدف به عقب بر می گردیم node، از طریق پدر و مادر خود، ردیابی مجدد تمام راه به شروع node. علاوه بر این، ما معکوس مسیری برای شهود خودمان برای رفتن از start_node به سمت target_nodeبا این حال، این مرحله اختیاری است.

از طرف دیگر، اگر مسیری وجود نداشته باشد، الگوریتم یک لیست خالی برمی گرداند.

با در نظر گرفتن پیاده سازی توضیح داده شده قبلی، می توانیم آن را با اجرای جستجوی BFS آزمایش کنیم روی نمودار مثال:

بیایید این نمودار را با استفاده از ما بازسازی کنیم Graph کلاس این یک گراف بدون جهت با 6 گره است، بنابراین ما آن را به صورت نمونه‌سازی می‌کنیم:

graph = Graph(6, directed=False)

در مرحله بعد، باید تمام لبه های نمودار را به نمونه اضافه کنیم Graph کلاسی که ما ایجاد کردیم:

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

حال، بیایید ببینیم چگونه Graph کلاس به صورت داخلی نمودار نمونه ما را نشان می دهد.

graph.print_adj_list()

این اراده print لیست مجاورتی که برای نشان دادن نموداری که ایجاد کرده ایم استفاده می شود:

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

در این لحظه، ما یک نمودار ایجاد کرده‌ایم و درک می‌کنیم که چگونه به عنوان یک ماتریس مجاورت ذخیره می‌شود. با در نظر گرفتن تمام این موارد، می توانیم خود جستجو انجام دهیم. بگویید می خواهیم جستجو کنیم node 5 شروع از node 0:

path = ()
path = graph.bfs(0, 5)
print(path)

اجرای این کد نتیجه می دهد:

(0, 3, 5)

پس از نگاهی گذرا به نمودار مثال، می‌توانیم ببینیم که کوتاه‌ترین مسیر بین 0 و 5 است در واقع (0, 3, 5). اگرچه، شما همچنین می توانید پیمایش کنید (0, 2, 5) و (0, 4, 5). این مسیرهای جایگزین اساساً همان فاصله هستند (0, 3, 5) – با این حال، روش مقایسه گره ها توسط BFS را در نظر بگیرید. از آن “اسکن” می کند چپ به راست و 3 اولین است node روی سمت چپ لیست مجاورت که به 5، بنابراین این مسیر به جای بقیه طی می شود.

این یکی از ویژگی های BFS است که می خواهید پیش بینی کنید. از چپ به راست جستجو می کند – و نمی خواهد یک مسیر به همان اندازه معتبر را پیدا کنید اگر “بعد از” مسیر اول پیدا شود.

در اینجا یک نمودار قطع شده به نظر می رسد:

اگر بخواهیم یک مسیر بین گره ها را جستجو کنیم 0 و 3 در این نمودار، آن جستجو ناموفق خواهد بود و یک مسیر خالی برگردانده می شود.

عرض-اول پیاده سازی – پیمایش نمودار

عرض-اولین پیمایش یک مورد خاص از Breadth-First Search است که مسیر را طی می کند کل نمودار، به جای جستجو برای یک هدف node. الگوریتم همانطور که قبلاً تعریف کرده بودیم باقی می ماند، تفاوت در این است که هدف را بررسی نمی کنیم. node و ما نیازی به یافتن مسیری نداریم که به آن منتهی شود.

این پیاده سازی را به طور قابل توجهی ساده می کند – اجازه دهید فقط print از هر کدام node برای به دست آوردن شهودی از روش عبور آن از گره ها عبور می شود:

def bfs_traversal(self, start_node):
    visited = set()
    queue = Queue()
    queue.put(start_node)
    visited.add(start_node)

    while not queue.empty():
        current_node = queue.get()
        print(current_node, end = " ")
        for (next_node, weight) in self.m_adj_list(current_node):
            if next_node not in visited:
                queue.put(next_node)
                visited.add(next_node)  

حالا بیایید نمودار مثال زیر را به شکلی که قبلا نشان داده شده است تعریف کنیم:

graph = Graph(5, directed=False)


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

در نهایت، اجازه دهید کد را اجرا کنیم:

graph.bfs_traversal(0)

اجرای این کد انجام خواهد شد print گره ها به ترتیبی که BFS آنها را اسکن کرد:

0 1 2 4 3

گام به گام

بیایید کمی عمیق تر به این مثال بپردازیم و ببینیم که چگونه الگوریتم گام به گام کار می کند. همانطور که پیمایش را از ابتدا شروع می کنیم node 0، آن را در قرار داده است visited تنظیم و به queue همچنین. در حالی که ما هنوز گره هایی در آن داریم queue، اولی را استخراج می کنیم، print و همه همسایگانش را بررسی کنید.

هنگام عبور از همسایگان، بررسی می کنیم که آیا هر یک از آنها بازدید شده است یا خیر، و در غیر این صورت آنها را به آنها اضافه می کنیم queue و آنها را به عنوان بازدید شده علامت گذاری کنید:

پیچیدگی زمانی

در حین عرض-اولین پیمایش، هر node دقیقا بازدید می شود یک بار، و هر شاخه نیز مشاهده می شود یک بار در صورت الف جهت دار نمودار، یعنی دو برابر اگر نمودار باشد بدون جهت. بنابراین، پیچیدگی زمانی الگوریتم BFS است O(|V| + |E|)، جایی که V مجموعه ای از گره های گراف است و E مجموعه ای است که از تمام شاخه های آن (لبه ها) تشکیل شده است.

نتیجه

در این درس، تئوری پشت الگوریتم جستجوی پهنا-اول را توضیح داده و مراحل آن را تعریف کرده‌ایم.

ما پیاده‌سازی Python را برای جستجوی Breadth-First و Breadth-First Traversal به تصویر کشیده‌ایم و آنها را آزمایش کرده‌ایم. روی نمودارها را مثال بزنید تا ببینید چگونه گام به گام کار می کنند. در نهایت پیچیدگی زمانی این الگوریتم را توضیح داده ایم.