بررسی جامع الگوریتم‌های پیمایش گراف - از کاربردها تا پیاده‌سازی در پایتون

الگوریتم‌های پیمایش گراف (Graph traversal) مانند جستجوی عمق اول (Depth First Search – DFS) و جستجوی سطح اول (Breadth First Search – BFS)، ابزارهایی قدرتمند برای بازدید از تمامی گره‌ها و یال‌های گراف و استخراج اطلاعات مورد نیاز از آن‌ها می‌باشند. الگوریتم DFS با پیشروی عمقی در شاخه‌های گراف و بازگشت به عقب برای بررسی مسیرهای دیگر، به یک درخت پوشا دست می‌یابد که تمامی گره‌ها را بدون تکرار یال‌ها نمایش می‌دهد. در مقابل، الگوریتم BFS با پیشروی سطحی، ابتدا تمامی گره‌های همسایه را بازدید کرده و سپس به سطوح بعدی می‌رود. این الگوریتم‌ها در بسیاری از مسائل علمی و عملی کاربرد دارند و درک صحیح آن‌ها می‌تواند به بهبود عملکرد در تحلیل و حل مسائل گرافی کمک کند. در این مقاله به بررسی این الگوریتم‌ها و نیز کاربردهای گسترده آن‌ها مانند یافتن مولفه‌های همبند قوی یا تشخیص دو بخشی بودن گراف خواهیم پرداخت.

فهرست مطالب پنهان‌کردن فهرست

1. گراف چیست؟
2. الگوریتم‌های پیمایش گراف
3. الگوریتم جستجوی عمق اول
4. الگوریتم جستجوی سطح اول
5. جمع‌بندی الگوریتم‌های پیمایش گراف
6. پیچیدگی زمانی و مکانی الگوریتم‌ها
7. مزایا و معایب الگوریتم‌های DFS و BFS
8. کلام آخر درباره الگوریتم‌های پیمایش گراف
9. پرسش‌های متداول
10. یادگیری تحلیل داده را از امروز شروع کنید!

گراف چیست؟

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

برای آشنایی بیشتر با گراف و انواع آن مطالعه مقاله نظریه گراف: پلی بین ریاضیات و دنیای واقعی را پیشنهاد می‌کنیم.

الگوریتم‌های پیمایش گراف

الگوریتم‌های پیمایش گراف (Graph traversal) به ما کمک می‌کنند تا تمامی گره‌ها و یال‌های یک گراف را بازدید کنیم و اطلاعات مورد نیاز را استخراج کنیم. این الگوریتم‌ها پایه و اساس بسیاری از مسائل مهم در علوم کامپیوتر و تحلیل داده‌ها هستند. با استفاده از این الگوریتم‌ها می‌توانیم به درک بهتری از ساختار و ویژگی‌های گراف‌ها برسیم و مسائل پیچیده‌ای مانند جستجوی مسیر، دور و غیره در گراف‌ها را حل کنیم.

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

الگوریتم جستجوی عمق اول (Depth First Search – DFS) یکی از الگوریتم‌های پیمایش گراف پایه‌ای برای گراف‌ها و درخت‌ها است. در این الگوریتم، جستجو از یک نقطه شروع می‌شود و به صورت عمقی به هر شاخه رفته و تا حد ممکن در همان شاخه پیش می‌رود تا به نقطه‌ای برسد که دیگر امکان پیشروی نباشد، آن‌گاه به نقاط قبلی بازمی‌گردد و مسیرهای دیگر را بررسی می‌کند.

تاریخچه الگوریتم جستجوی عمق اول

الگوریتم جستجوی عمق اول (DFS) یکی از قدیمی‌ترین و پرکاربردترین روش‌های جستجو در علوم کامپیوتر است. ریشه‌های این الگوریتم به سال‌های اولیهٔ دههٔ ۱۹۵۰ برمی‌گردد. نخستین بار، این الگوریتم به صورت ضمنی در پژوهش‌های مربوط به نظریه گراف‌ها مطرح شد. جستجوی اول عمق به طور رسمی در سال ۱۹۵۹ توسط یک ریاضی‌دان به نام ادوارد مور (Edward F. Moore) در دانشگاه پنسیلوانیا معرفی شد. او این روش را به عنوان بخشی از تحقیق خود در زمینهٔ ماشین‌های متناهی و نظریهٔ زبان‌های رسمی مطرح کرد.

پس از معرفی اولیه، الگوریتم DFS به سرعت توجه دانشمندان علوم کامپیوتر را به خود جلب کرد. در دههٔ ۱۹۷۰، پژوهشگران بیشتری به توسعه و بهبود این الگوریتم پرداختند. رابرت تارچن (Robert Tarjan) یکی از افراد برجسته‌ای بود که در این زمینه فعالیت کرد. او در سال ۱۹۷۲ از این الگوریتم برای حل مسائل مختلفی نظیر یافتن مولفه‌های قویا همبند در گراف‌ها استفاده کرد. نتایج کارهای تارچن باعث شد تا DFS به عنوان یک ابزار قدرتمند در تحلیل و حل مسائل گرافی شناخته شود.

خروجی الگوریتم جستجوی عمق اول

هنگامی که الگوریتم جستجوی عمق اول یا همان DFS از یک گره شروع به کار می‌کند و به صورت بازگشتی به تمامی گره‌های قابل دسترس در گراف می‌رود، مسیری از گره‌ها و یال‌ها تشکیل می‌شود که یک درخت پوشا (Spanning Tree) است. این درخت پوشا شامل تمامی گره‌های گراف می‌شود و حداقل تعداد یال‌ها را دارد به طوری که تمام گره‌ها به هم متصل باشند و هیچ حلقه‌ای در گراف ایجاد نشود. به عبارتی دیگر، خروجی DFS می‌تواند به عنوان یک درخت پوشا در نظر گرفته شود که مسیرهای پیمایش شده در گراف را بدون تکرار یال‌ها و ایجاد چرخه نمایش می‌دهد.

الگوریتم جستجوی عمق اول چطور کار می‌کند؟

الگوریتم DFS از یک گره شروع می‌کند که به عنوان گره آغازین انتخاب می‌شود. این گره می‌تواند هر گره‌ای از گراف باشد (پس خروجی الگوریتم DFS منحصربه‌فرد نیست). در بیشتر پیاده‌سازی‌ها، این گره به عنوان گره «ریشه» یا گره «مبدا» شناخته می‌شود. از گره مبدا، به یکی از گره‌های همسایه پیش می‌رویم. این فرایند تا زمانی ادامه پیدا می‌کند که به یک گره برسیم که هیچ همسایه‌ای نداشته باشد که هنوز بازدید نشده باشد. این به معنای پیشروی به عمق گراف است. زمانی که به گرهی می‌رسیم که هیچ همسایه‌ای ندارد که هنوز بازدید نشده باشد، به گره قبلی بازمی‌گردیم و دیگر همسایه‌های آن را بررسی می‌کنیم. این فرایند بازگشت به عقب (Back tracking) نامیده می‌شود. گره‌های پیمایش شده را علامت‌گذاری می‌کنیم تا از بازدید مجدد آن‌ها جلوگیری شود. این علامت‌گذاری می‌تواند با استفاده از یک مجموعه یا لیست (اغلب به‌ نام visited) انجام شود.

بررسی گام‌به‌گام مراحل اجرای الگوریتم جستجوی عمق اول

حال بیایید کمی عمیق‌تر روند اجرای الگوریتم DFS را مرور کنیم. برای این منظور فرض کنید یک گراف به‌شکل زیر داریم:

گسترش گره

برای اجرای الگوریتم DFS نیاز به یک پشته (stack) و یک لیست به‌نام visited برای علامت‌گذاری گره‌ها به‌عنوان ملاقات‌شده داریم. در گام نخست یک گره دلخواه را انتخاب کرده (مثلا گره صفر) و آن را در پشته قرار می‌دهیم (stack.push). سپس چون گره دیگری در پشته نیست، همین گره را گسترش می‌دهیم، به‌این معنی که آن را از پشته خارج (stack.pop) و – درصورتی که تاکنون ملاقات نشده – به‌عنوان ملاقات شده علامت‌گذاری می‌کنیم.

پردازش گره و تولید همسایه‌های آن

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

تکرار مراحل بالا برای سایر گره‌ها

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

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

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

در قسمت بعد گره چهار را که در بالای پشته است، گسترش می‌دهیم. به‌این‌ترتیب گره چهار در لیست ملاقات‌شده‌ها قرار می‌گیرد و چون تنها همسایه‌‌اش (یعنی گره دو) قبلا به‌عنوان ملاقات‌شده‌ علامت خورده، کار دیگری انجام نمی‌شود:

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

با خالی شدن پشته، الگوریتم جستجوی عمق اول به پایان می‌رسد.

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

پیاده‌سازی الگوریتم DFS به عنوان یکی از الگوریتم‌های پیمایش گراف می‌تواند به صورت بازگشتی یا غیربازگشتی انجام شود. در روش بازگشتی، از فراخوانی توابع استفاده می‌شود، درحالی‌که در روش غیربازگشتی، از یک ساختار داده‌ای پشته به‌صورت صریح استفاده می‌شود.

پیاده‌سازی الگوریتم جستجوی عمق اول به‌ صورت غیربازگشتی

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

برای این منظور ابتدا یک تابع به‌ نام dfs_iterative تعریف می‌کنیم که گراف مورد نظر و گره شروع (یک گره دلخواه) را به‌ عنوان ورودی دریافت می‌کند. در ابتدای این تابع یک لیست به‌نام visited تعریف می‌کنیم که همان‌طور که توضیح دادیم، نقش ذخیره گره‌های بازدیدشده را دارد. لیست دیگری به‌عنوان پشته به‌ نام stack نیز تعریف می‌کنیم که بعد از تولید همسایه‌های گره جاری، آن‌ها در آن قرار دهیم. سپس در یک حلقه while که تا خالی‌شدن کامل پشته برقرار خواهد بود، گره جاری را گسترش می‌دهیم. یعنی آن را از پشته pop کرده و در صورتی که تاکنون ملاقات نشده، آن را به‌ لیست ملاقات‌شده‌ها اضافه می‌کنیم. اکنون می‌توان گره ملاقات‌شده را پردازش کرد. ما در اینجا برای سادگی عمل پردازش را چاپ (print) گره تعریف می‌کنیم. در پایان نیز همسایه‌های ملاقات‌نشده گره را به پشته اضافه می‌کنیم:

def dfs_iterative(graph, start):
  # a list to store visited nodes
  visited = []
  # put the initial node in the stack
  stack = [start]
  # repeat until the stack is empty
  while stack:
    # extend the node
    node = stack.pop()
    # check if the node is not visited
    if node not in visited:
      # mark the node as visited
      visited.append(node)
      print(f'Process node: {node}') # or any other process
      # produce nodes
      stack.extend(sorted([n for n in graph[node] if n not in visited], reverse=True))
      print(f'Stack: {stack}, Visited: {visited}\n')

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

# Define the graph with nodes
graph = {
  0: [1, 2, 3],
  1: [0, 2],
  2: [0, 1, 4],
  3: [0],
  4: [2]
}

dfs_iterative(graph, 0)

Process node: 0
Stack: [3, 2, 1], Visited: [0]
Process node: 1
Stack: [3, 2, 2], Visited: [0, 1]
Process node: 2
Stack: [3, 2, 4], Visited: [0, 1, 2]
Process node: 4
Stack: [3, 2], Visited: [0, 1, 2, 4]
Process node: 3
Stack: [], Visited: [0, 1, 2, 4, 3]

بررسی خروجی الگوریتم جستجوی عمق اول به‌ صورت غیربازگشتی

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

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

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

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

def dfs_recursive(graph, start, visited=None):
  # a list to store visited nodes
  if visited is None:
    visited = []
  # mark the node as visited
  visited.append(start)
  print(f'Process node: {start}') # or any other process
  # recursively visit all the unvisited neighbors of the current node
  for neighbor in graph[start]:
    if neighbor not in visited:
      dfs_recursive(graph, neighbor, visited)

برای مشاهده خروجی کد بالا به صورت زیر عمل می‌کنیم:

# Define the graph with nodes
graph = {
  0: [1, 2, 3],
  1: [0, 2],
  2: [0, 1, 4],
  3: [0],
  4: [2]
}
dfs_recursive(graph, 0)

Process node: 0
Process node: 1
Process node: 2
Process node: 4
Process node: 3

کاربردهای الگوریتم جستجوی عمق اول

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

تشخیص وجود مسیر

یکی از کاربردهای الگوریتم DFS، یافتن یک مسیر از یک گره به گره دیگر در یک گراف است. DFS گره‌ها را به ترتیب عمق بازدید می‌کند تا به گره هدف برسد. این روش در مسائلی که نیاز به بررسی همه مسیرهای ممکن از یک نقطه شروع تا یک نقطه هدف داریم، مفید است.

چطور با جستجوی عمق ‌اول یک مسیر را در یک گراف پیدا کنیم؟

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

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

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

def dfs_search(graph, start, target):
  # a list to store visited nodes
  visited = []
  # put the initial node in the stack
  stack = [start]
  while stack:
    # extend the node
    node = stack.pop()
    # process the node
    if node == target:
      return True
    # check if the node is not visited
    if node not in visited:
      # mark the node as visited
      visited.append(node)
      # produce nodes
      stack.extend(sorted([n for n in graph[node] if n not in visited], reverse=True))
  return False

خروجی کد بالا روی گراف مورد نظر را به صورت زیر می‌توان دید:

# Define the graph with nodes
graph = {
  0: [1, 2, 3],
  1: [0, 2],
  2: [0, 1, 4],
  3: [0],
  4: [2]
}

result = dfs_search(graph, 0, 4)
print("Found target:", result)

Found target: True

تشخیص دو بخشی‌بودن گراف

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

برای آشنایی بیشتر با گراف‌های دو بخشی، می‌توانید مقاله نظریه گراف: پلی بین ریاضیات و دنیای واقعی را بخوانید.

چطور با جستجوی عمق اول تشخیص دهیم یک گراف دو بخشی است؟

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

پیاده‌سازی الگوریتم تشخیص دو بخشی بودن گراف با جستجوی عمق اول در پایتون

برای پیاده‌سازی الگوریتم تشخیص دو بخشی بودن گراف با استفاده از جستجوی عمق ‌اول از دو تابع اصلی dfs_bipartite و is_bipartite استفاده می‌کنیم. در تابع dfs_bipartite، هر گره را با رنگی (کدشده با ۰ و ۱) مشخص می‌کنیم و سپس به صورت بازگشتی همسایه‌های آن گره را با رنگ مخالف بازدید می‌کنیم. اگر در طی این بازدید به گره‌ای برسیم که قبلاً بازدید شده و رنگ آن با رنگ فعلی مطابقت داشته باشد (یعنی رنگ یک گره با رنگ همسایه‌اش یکی شود)، گراف دو بخشی نیست و تابع False برمی‌گرداند. در غیر این صورت، پس از بازدید از تمامی همسایه‌ها، تابع True برمی‌گرداند. تابع is_bipartite مجموعه‌ای از گره‌های بازدید شده را نگهداری می‌کند و برای هر گره در گراف، اگر بازدید نشده باشد، تابع dfs_bipartite را با رنگ ابتدایی ۰ فراخوانی می‌کند. اگر گراف دو بخشی باشد، True برمی‌گرداند، در غیر این صورت False برمی‌گرداند:

def dfs_bipartite(graph, node, color, colors, visited):
  # color the node
  colors[node] = color
  # mark the node as visited
  visited.append(node)
  for neighbor in graph[node]:
    if neighbor not in visited:
      if not dfs_bipartite(graph, neighbor, 1 - color, colors, visited): # swap color
        return False
    # if the color doesn't match, the graph is not bipartite
    elif colors[neighbor] == color:
      return False
  return True

def is_bipartite(graph):
  # dictionary to store the colors of nodes
  colors = {}
  # list to store visited nodes
  visited = []
  # recursively visit all the unvisited nodes of the graph
  for node in graph:
    if node not in visited:
      if not dfs_bipartite(graph, node, 0, colors, visited): # start DFS with color 0
        return False
  return True

خروجی کد بالا روی گراف زیر را در ادامه می‌توانید ببینید:

# Define the graph with nodes and edges
graph = {
  'A': ['C', 'D', 'E'],
  'B': ['C', 'D', 'E'],
  'C': ['A', 'B'],
  'D': ['A', 'B'],
  'E': ['A', 'B']
}

result = is_bipartite(graph)
print("Is the graph bipartite?", result)

Is the graph bipartite? True

تشخیص دور

تشخیص دور (Cycle Detection) در گراف یکی دیگر از کاربردهای مهم الگوریتم جستجوی عمق اول است. این ویژگی به ما کمک می‌کند تا بررسی کنیم که آیا یک گراف شامل دور است یا خیر. این کاربرد در تحلیل پایداری سیستم‌ها و شبکه‌ها، جلوگیری از حلقه‌های بی‌نهایت در برنامه‌های کامپیوتری و تحلیل وابستگی‌ها در پروژه‌ها اهمیت زیادی دارد.

چطور با جستجوی عمق اول تشخیص دهیم یک گراف دور دارد؟

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

پیاده‌سازی الگوریتم تشخیص دور در گراف با جستجوی عمق اول در پایتون

برای پیاده‌سازی الگوریتم تشخیص حلقه در گراف با استفاده از جستجوی عمق ‌اول (DFS) از دو تابع اصلی dfs_cycle_detect و has_cycle استفاده می‌کنیم. در تابع dfs_cycle_detect، از هر گره شروع کرده و به صورت بازگشتی همسایه‌های آن گره را بازدید می‌کنیم. اگر در طی این بازدید به گره‌ای برسیم که قبلاً بازدید شده و والد فعلی گره نباشد، دور در گراف شناسایی می‌شود و تابع True برمی‌گرداند. در غیر این صورت، پس از بازدید از تمامی همسایه‌ها، تابع False برمی‌گرداند. تابع has_cycle مجموعه‌ای از گره‌های بازدید شده را نگهداری می‌کند و برای هر گره در گراف، اگر بازدید نشده باشد، تابع dfs_cycle_detect را فراخوانی می‌کند. اگر حلقه‌ای در هر یک از این بازدیدها شناسایی شود، True برمی‌گرداند، در غیر این صورت False برمی‌گرداند:

def dfs_cycle_detect(graph, node, visited, parent):
  # Mark the node as visited
  visited.append(node)
  # Traverse neighbors
  for neighbor in graph[node]:
    if neighbor not in visited:
      # Recursively visit the neighbor
      if dfs_cycle_detect(graph, neighbor, visited, node):
        return True
    elif parent is not None and neighbor != parent:
      # If the neighbor is visited and it is not the parent, a cycle is detected
      return True
  return False

def has_cycle(graph):
  # List to keep track of visited nodes
  visited = []
  for node in graph:
    if node not in visited:
      if dfs_cycle_detect(graph, node, visited, None):
        return True
  return False

خروجی کد بالا روی گراف زیر را در ادامه می‌توانید ببینید:

# Define the graph with nodes and directed edges using lists
graph = {
  'A': ['B'],
  'B': ['C', 'D'],
  'C': ['A'], # Cycle: A -> B -> C -> A
  'D': []
}

result = has_cycle(graph)
print("Does the graph have a cycle?", result)

Does the graph have a cycle? True

تشخیص مولفه‌های قویا همبند گراف

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

چطور با جستجوی عمق اول مولفه‌های قویا همبند یک گراف را تشخیص دهیم؟

درواقع الگوریتم DFS در ضمن الگوریتم کساراجو (Kosaraju Algorithm) استفاده می‌شود. این الگوریتم برای پیدا کردن اجزای قویاً همبند در یک گراف جهت‌دار استفاده می‌شود و شامل سه مرحله اصلی است. در مرحله اول، یک پیمایش عمق ‌اول (DFS) بر روی گراف اصلی انجام می‌شود و گره‌ها بر اساس زمان پایان بازدیدشان به ترتیب در یک پشته قرار می‌گیرند. در الگوریتم جستجوی عمق ‌اول، زمان پایان به زمانی اشاره دارد که ما یک گره و تمام همسایه‌های آن را ملاقات کرده‌ایم. این مفهوم برای مرتب‌سازی گره‌ها در گراف استفاده می‌شود. البته ما دقیقا از زمان استفاده نمی‌کنیم و ترتیب اتمام کامل پردازش گره‌ها برای‌مان مهم است. این ترتیب با استفاده از push کردن گره‌ها به یک پشته حفظ می‌گردد.

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

پیاده‌سازی الگوریتم تشخیص مولفه‌های قویا همبند گراف با جستجوی عمق اول در پایتون

برای پیاده‌سازی الگوریتم کوساراجو برای یافتن اجزای قویا همبند در یک گراف جهت‌دار از دو تابع اصلی dfs و reverse_graph استفاده می‌کنیم. ابتدا در تابع dfs، هر گره را بازدید کرده و به لیست بازدید شده‌ها اضافه می‌کنیم. اگر component فراهم شده باشد، گره جاری را به آن اضافه می‌کنیم. سپس به صورت بازگشتی تمامی همسایه‌های آن گره را بازدید می‌کنیم و در نهایت، گره جاری را به پشته اضافه می‌کنیم.

در مرحله دوم، تابع reverse_graph را تعریف می‌کنیم که جهت تمامی یال‌های گراف ورودی را معکوس می‌کند. سپس مجموعه بازدید شده‌ها پاک می‌شود تا بتوانیم دوباره از آن استفاده کنیم. در مرحله سوم، گره‌ها را بر اساس ترتیب موجود در پشته (که نشان‌دهنده ترتیب پایان بازدید در مرحله اول است) بازدید می‌کنیم. اگر گره‌ای بازدید نشده باشد، DFS را روی گراف معکوس از آن گره شروع می‌کنیم و تمامی گره‌های مرتبط با آن گره را به لیست component اضافه می‌کنیم که نشان‌دهنده یک جزء قویاً همبند است. در نهایت، لیست اجزای قویا همبند برگردانده می‌شود.

def kosaraju_scc(graph):

  def dfs(node, graph, visited, stack=None, component=None):
    # Mark the node as visited
    visited.append(node)
    if component is not None:
      # Collect the node if component is provided
      component.append(node)
    for neighbor in graph[node]:
      if neighbor not in visited:
        dfs(neighbor, graph, visited, stack, component)
    if stack is not None:
      # Add the node to the stack after visiting all neighbors
      stack.append(node)

  def reverse_graph(graph):
    reversed_graph = {node: [] for node in graph}
    for node in graph:
      for neighbor in graph[node]:
        reversed_graph[neighbor].append(node)
    return reversed_graph

  # Step 1: Order nodes by finish time in decreasing order
  stack = []
  visited = []
  for node in graph:
    if node not in visited:
      dfs(node, graph, visited, stack)
  # Step 2: Reverse the graph
  reversed_graph = reverse_graph(graph)
  # Step 3: Process all nodes in decreasing order of finish time
  visited.clear()
  sccs = []
  while stack:
    node = stack.pop()
    if node not in visited:
      component = []
      dfs(node, reversed_graph, visited, component=component)
      sccs.append(component)
  return sccs

خروجی کد بالا روی گراف زیر را در ادامه می‌توانید ببینید:

# Define the graph with nodes and directed edges
graph = {
  'A': ['B'],
  'B': ['C'],
  'C': ['A', 'D'],
  'D': ['E', 'F'],
  'E': ['G'],
  'F': ['D', 'G'],
  'G': ['E']
}

sccs = kosaraju_scc(graph)
print("Strongly Connected Components:", sccs)

Strongly Connected Components: [[‘A’, ‘C’, ‘B’], [‘D’, ‘F’], [‘E’, ‘G’]]

مرتب‌سازی توپولوژیکی

یکی از کاربردهای مهم الگوریتم جستجوی عمق اول، مرتب‌سازی توپولوژیکی (Topological sorting) است. این مرتب‌سازی برای گراف‌های بدون حلقه جهت‌دار (Directed Acyclic Graph – DAG) استفاده می‌شود و ترتیب خطی گره‌ها را به گونه‌ای پیدا می‌کند که اگر یک گره به گره دیگری اشاره داشته باشد، گره اول قبل از گره دوم قرار گیرد. این الگوریتم در برنامه‌ریزی وظایف، تحلیل پیش‌نیازها و ساختارهای سلسله مراتبی کاربرد دارد.

چطور با جستجوی عمق اول ترتیب توپولوژیکی یک گراف را پیدا کنیم؟

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

پیاده‌سازی الگوریتم تشخیص ترتیب توپولوژیکی گراف با جستجوی عمق اول در پایتون

برای پیاده‌سازی الگوریتم ترتیب توپولوژیکی با استفاده از جستجوی عمق ‌اول (DFS) به عنوان یکی از الگوریتم‌های پیمایش گراف از دو تابع اصلی dfs_recursive و topological_sort_dfs استفاده می‌کنیم. در تابع dfs_recursive، هر گره را بازدید کرده و به لیست بازدید شده‌ها اضافه می‌کنیم. سپس به صورت بازگشتی تمامی همسایه‌های آن گره را بازدید می‌کنیم. پس از بازدید از تمامی همسایه‌ها، گره جاری را به پشته اضافه می‌کنیم. در نهایت، با تابع topological_sort_dfs لیستی از گره‌های بازدید شده را نگهداری کرده و برای هر گره در گراف، اگر بازدید نشده باشد، تابع dfs_recursive را فراخوانی می‌کنیم. پس از اتمام بازدید از تمامی گره‌ها، پشته را معکوس کرده و به عنوان نتیجه برمی‌گردانیم که نشان‌دهنده ترتیب توپولوژیکی گراف است:

def dfs_recursive(graph, start, visited=None, stack=None):
  # a list to store visited nodes
  if visited is None:
    visited = []
  # mark the node as visited
  visited.append(start)
  # a stack to keep track of the nodes for topological sorting
  if stack is None:
    stack = []
  # recursively visit all the neighbors of the current node, if the node is unvisited
  for neighbor in graph[start]:
    if neighbor not in visited:
      dfs_recursive(graph, neighbor, visited, stack)
  # add the node to the stack after visiting neighbors
  stack.append(start)

def topological_sort_dfs(graph):
  visited = [] # a list to mark nodes as visited
  stack = [] # a stack to store the topological order
  # perform DFS algorithm for each node in the graph
  for node in graph:
    if node not in visited:
      dfs_recursive(graph, node, visited, stack)
  # return the stack in reverse order for topological sorting
  return stack[::-1]

خروجی کد بالا روی گراف زیر را در ادامه می‌توانید ببینید:

# Define the graph with nodes
graph = {
  'A': ['C', 'D'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': ['F'],
  'E': ['F'],
  'F': []
}

topological_order = topological_sort_dfs(graph)
print("Topological Order:", topological_order)

Topological Order: [‘B’, ‘E’, ‘A’, ‘D’, ‘C’, ‘F’]

الگوریتم جستجوی سطح اول

الگوریتم جستجوی سطح اول (Breadth First Search – BFS) به عنوان یکی از الگوریتم‌های پیمایش گراف پایه‌ای برای گراف‌ها و درخت‌ها است. در این الگوریتم، جستجو از یک نقطه شروع می‌شود و به صورت سطحی به هر گره همسایه می‌رود، سپس به سطح بعدی می‌رود و این فرآیند را تکرار می‌کند تا تمام گره‌ها بازدید شوند.

تاریخچه الگوریتم جستجوی سطح اول

الگوریتم جستجوی اول سطح (BFS) در دهه ۱۹۵۰ توسط ادوارد مور و کلود شانون (Claude Shannon) برای مطالعه ماشین‌های متناهی (Finite State Machines) و نظریه اطلاعات معرفی شد. در دههٔ ۱۹۷۰، الگوریتم BFS تحت تأثیر پژوهش‌های گسترده و بهبودهای مداوم قرار گرفت. یکی از محققین برجسته در این حوزه رابرت تارچن (Robert Tarjan) بود که با بررسی و بهبود الگوریتم‌های مرتبط، توانست کاربردهای جدیدی برای BFS ارائه دهد. کارهای تارچن نه تنها بر DFS، بلکه بر BFS نیز تأثیرگذار بود و باعث شد تا این الگوریتم به‌عنوان یکی از ابزارهای اصلی در تحلیل و حل مسائل گرافی شناخته شود.

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

خروجی الگوریتم جستجوی سطح اول

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

الگوریتم جستجوی سطح اول چطور کار می‌کند؟

الگوریتم BFS از یک گره شروع می‌کند که به عنوان گره آغازین انتخاب می‌شود. این گره می‌تواند هر گره‌ای از گراف باشد. در بیشتر پیاده‌سازی‌ها، این گره به عنوان گره «ریشه» یا گره «مبدا» شناخته می‌شود. از گره مبدا، به تمامی گره‌های همسایه پیش می‌رویم. این فرایند تا زمانی ادامه پیدا می‌کند که به یک گره برسیم که هیچ همسایه‌ای نداشته باشد که هنوز بازدید نشده باشد. این به معنای پیشروی به سطح بعدی گراف است. زمانی که به گرهی می‌رسیم که هیچ همسایه‌ای ندارد که هنوز ملاقات نشده باشد، به گره قبلی بازمی‌گردیم و دیگر همسایه‌های آن را بررسی می‌کنیم. گره‌های پیمایش شده را علامت‌گذاری می‌کنیم تا از بازدید مجدد آن‌ها جلوگیری شود. این علامت‌گذاری می‌تواند با استفاده از یک مجموعه یا لیست (اغلب به‌نام visited) انجام شود.