الگوریتم جستجوی اول عمق ⚡️ آموزش الگوریتم dfs گراف

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

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

الگوریتم جستجوی اول عمق، تمام گره‌های گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ...  را در دو دسته قرار می‌دهد:

• گره‌های ویزیت شده (Visited)
• گره‌های ویزیت نشده (Not Visited)

هدف این الگوریتم این است که تمام گره‌ها را در دسته ویزیت شده قرار دهد. نحوه کارکرد این الگوریتم به‌صورت زیر است:

• گره شروع را در بالای پشتهساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان دادهاین مقاله عالی توضیح داده که پشته چیست و کاربرد پشته در ساختمان داده چیست، همچنین نحوه کارکرد پشته، پیاده سازی پشته و عملیات های پشته را معرفی کرده قرار می‌دهیم.
• گره بالای پشته را برمی‌داریم و آن را در دسته ویزیت شده قرار می‌دهیم.
• تمام گره‌هایی که همسایه گره ویزیت شده هستند و هنوز ویزیت نشده‌اند را در بالای پشته قرار می‌دهیم.
• مراحل 2 و 3 را تا زمانی که پشته خالی شود تکرار می‌کنیم.

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

حال با یک مثال، نحوه عملکرد الگوریتم جستجوی اول عمق را بررسی می‌کنیم. در این مثال ما از یک گراف با 5 گره استفاده می‌کنیم.

از گره 0 شروع می‌کنیم. الگوریتم DFS گره 0 را در دسته ویزیت شده قرار می‌دهد و همسایه‌های آن را در پشته می‌گذارد.

حال گره بالای پشته که 1 است را ویزیت می‌کنیم و همسایه‌هایش را بررسی می‌کنیم. از آنجایی که گره 0 قبلا ویزیت شده‌است، ما گره 2 را ویزیت می‌کنیم.

گره 2، گره همسایه 4 را دارد که هنوز ویزیت نشده است؛ آن را در بالای پشته قرارداده و ویزیت می‌کنیم.

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

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

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

Pseudocode

شبه کد الگوریتم DFS در زیر نشان داده شده است. در تابع init() ما برای هر گره گراف، الگوریتم DFS را اجرا می‌کنیم تا مطمئن شویم حتی اگر گراف ناهمبند هم باشد، این الگوریتم به‌درستی برای همه گره‌ها اجرا خواهد شد.

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

کپی کردن کد

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

Python

# DFS algorithm in Python


# DFS algorithm
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited


graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')

# DFS algorithm in Python


# DFS algorithm
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited


graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')

کپی کردن کد

Java

// DFS algorithm in Java

import java.util.*;

class Graph {
  private LinkedList<Integer> adjLists[];
  private boolean visited[];

  // Graph creation
  Graph(int vertices) {
    adjLists = new LinkedList[vertices];
    visited = new boolean[vertices];

    for (int i = 0; i < vertices; i++)
      adjLists[i] = new LinkedList<Integer>();
  }

  // Add edges
  void addEdge(int src, int dest) {
    adjLists[src].add(dest);
  }

  // DFS algorithm
  void DFS(int vertex) {
    visited[vertex] = true;
    System.out.print(vertex + " ");

    Iterator<Integer> ite = adjLists[vertex].listIterator();
    while (ite.hasNext()) {
      int adj = ite.next();
      if (!visited[adj])
        DFS(adj);
    }
  }

  public static void main(String args[]) {
    Graph g = new Graph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    System.out.println("Following is Depth First Traversal");

    g.DFS(2);
  }
}

// DFS algorithm in Java

import java.util.*;

class Graph {
  private LinkedList<Integer> adjLists[];
  private boolean visited[];

  // Graph creation
  Graph(int vertices) {
    adjLists = new LinkedList[vertices];
    visited = new boolean[vertices];

    for (int i = 0; i < vertices; i++)
      adjLists[i] = new LinkedList<Integer>();
  }

  // Add edges
  void addEdge(int src, int dest) {
    adjLists[src].add(dest);
  }

  // DFS algorithm
  void DFS(int vertex) {
    visited[vertex] = true;
    System.out.print(vertex + " ");

    Iterator<Integer> ite = adjLists[vertex].listIterator();
    while (ite.hasNext()) {
      int adj = ite.next();
      if (!visited[adj])
        DFS(adj);
    }
  }

  public static void main(String args[]) {
    Graph g = new Graph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    System.out.println("Following is Depth First Traversal");

    g.DFS(2);
  }
}

کپی کردن کد

C

// DFS algorithm in C++

#include <iostream>
#include <list>
using namespace std;

class Graph {
  int numVertices;
  list<int> *adjLists;
  bool *visited;

   public:
  Graph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};

// Initialize graph
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
  visited = new bool[vertices];
}

// Add edges
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_front(dest);
}

// DFS algorithm
void Graph::DFS(int vertex) {
  visited[vertex] = true;
  list<int> adjList = adjLists[vertex];

  cout << vertex << " ";

  list<int>::iterator i;
  for (i = adjList.begin(); i != adjList.end(); ++i)
    if (!visited[*i])
      DFS(*i);
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 3);

  g.DFS(2);

  return 0;
}

// DFS algorithm in C++

#include <iostream>
#include <list>
using namespace std;

class Graph {
  int numVertices;
  list<int> *adjLists;
  bool *visited;

   public:
  Graph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};

// Initialize graph
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
  visited = new bool[vertices];
}

// Add edges
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_front(dest);
}

// DFS algorithm
void Graph::DFS(int vertex) {
  visited[vertex] = true;
  list<int> adjList = adjLists[vertex];

  cout << vertex << " ";

  list<int>::iterator i;
  for (i = adjList.begin(); i != adjList.end(); ++i)
    if (!visited[*i])
      DFS(*i);
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 3);

  g.DFS(2);

  return 0;
}

کپی کردن کد

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

پیچیدگی زمانی این الگوریتم برای گراف از مرتبه O(V+E) است که V تعداد گره‌ها و E تعداد یال‌های گراف است. برای درخت، پیچیدگی زمانی این الگوریتم از مرتبه O(V) است.

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

الگوریتم DFS کاربردهای زیادی در زمینه علوم کامپیوتر دارد که در زیر ما به بررسی برخی از آنها می‌پردازیم.

پیدا کردن دور در گراف

اگر ما در یک گراف، حین DFS به یک یال Back برخورد کنیم، گراف دور دارد. یال Back یالی است از گره فرزند یا نوه به گره پدر یا پدربزرگ.

پبدا کردن مسیر

می‌توانیم از الگوریتم DFS برای پیدا کردن مسیر بین دو گره U و V استفاده کنیم. مراحل پیدا کردن این مسیر به شکل زیر است:

• تابع DFS(G, U) را صدا زده و گره U را به عنوان گره شروع در نظر می‌گیریم.
• از یک پشته برای ذخیره کردن مسیر از گره اول تا گره فعلی استفاده می‌کنیم.
• به‌محض اینکه گره V پیدا شد، مسیر را به‌عنوان جواب برمی‌گردانیم.

مرتب کردن توپولوژیک

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

کراولرهای وب

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

پیدا کردن مولفه‌های متصل قوی در گراف

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

تولید ماز

الگوریتم DFS می‌تواند برای تولید مازهای تصادفی استفاده شود.

بک‌ترک

الگوریتم DFS می‌تواند در الگوریتم‌های بک‌ترک استفاده شود.

بررسی دوبخشی بودن گراف

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

انواع جستجوی اول عمق

جستجوی عمق اول ساده

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

جستجوی عمق اول با عمق محدود

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

جستجوی اول عمق تکرار شونده

در جستجوی عمق اول با عمق محدود، اگر گره جواب در عمقی پایین‌تر از عمق مشخص شده برای جستجو باشد (فرض کنید عمق محدود مشخص شده 5 و جواب در عمق 7 باشد)، الگوریتم جواب را پیدا نمی‌کند. برای حل این مشکل از الگوریتم جستجوی اول عمق تکرار شونده استفاده می‌کنیم. نحوه کارکرد این الگوریتم به این صورت است که ابتدا محدودیت عمق را روی 1 تنظیم کرده و جستجو را انجام می‌دهد. در صورتیکه جواب پیدا نشود، عمق را یکی افزایش داده و برابر 2 قرار می‌دهد و دوباره جستجو را انجام می‌دهد. مرحله افزایش عمق را تا جایی که به پاسخ برسد یا فضای مسئله به پایان برسد انجام می‌دهد.

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

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

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

• تضمینی برای یافتن پاسخ نمی‌دهد.
• ممکن است وارد حلقه بی‌نهایت شود.

جمع‌بندی

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

مطالب مرتبط

همه مقالات

فیلم‌های آموزشی ساختمان داده‌

مثال برنامه نویسی پایتون ⚡️ نمونه سوال پایتون با جواب

الگوریتم جنگل تصادفی ⚡️ الگوریتم جنگل چیست

آموزش تقسیم و غلبه، کاربردها و مزایای تقسیم و غلبه