کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

در این مقاله عالی الگوریتم جستجوی اول عمق بررسی و الگوریتم dfs گراف آموزش داده شده و مثال ها و پیاده سازی و کاربردهای الگوریتم جستجوی اول (DFS) عمق بیان شده

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

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

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

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

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

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

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

تصویر گرافی با 5 گره که به عنوان مثالی برای نحوه عملکرد الگوریتم جستجوی اول عمق آورده شده است

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

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

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

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

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

در این مرحله از الگوریتم جستجوی عمق اول، گره 4 که همسایه گره 2 است در بالای پشته قرار می گیرد

حال باید گره 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 را با 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')

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

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;
}

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

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

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

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

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

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

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

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

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

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

کراولرهای وب

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

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

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

تولید ماز

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

بک‌ترک

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

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

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

 

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

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

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

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

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

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

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

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

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

جمع‌بندی

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

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

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

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

3 روش برای جستجوی اول عمق وجود دارد: In-Order ،Pre-Order ،Post-Order

الگوریتم جستجوی اول عمق با عمق محدود چیست؟

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

در الگوریتم DFS از چه ساختمان داده‌ای استفاده می‌شود؟

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200