برنامه مسیر ۸ ماهه تا کنکور: مشاوره خصوصیت با استاد رضوی رو رزرو کن!
رزرو مشاوره
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

الگوریتم جستجوی اول سطح چیست؟ پیمایش سطحی (BFS) چیست؟

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

الگوریتم جستجوی اول سطح (BFS) برای جستجو در ساختمان دادهآموزش ساختمان داده و الگوریتمآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است درخت یا گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ...، برای پیدا کردن گره هدف استفاده می‌شود. این الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد از ریشه درخت یا گراف شروع گرده و قبل از رفتن به گره‌ها در عمق بعدی، همه گره‌ها را در عمق فعلی جستجو یا بازدید می‌کند. جستجوی اول سطح می‌تواند برای حل بسیاری از مسائل در نظریه گرافهمه چیز در مورد نظریه گراف (Graph Theory)همه چیز در مورد نظریه گراف (Graph Theory)در این مقاله یک مقدمه جامع در رابطه با نظریه گراف ارائه شده است و سعی شده نشان داده شود که دانستن برخی از مبانی نظریه گراف تا چه میزان می­‌تواند مفید و موثر باشد. استفاده شود. در این مقاله ما به معرفی و بررسی این الگوریتم می‌پردازیم.

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

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

الگوریتم جستجوی اول سطح، تمام گره‌های گراف را در دو دسته قرار می‌دهد.

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

  1. گره شروع را در صف قرار می‌دهیم.
  2. گره اول صف را برمی‌داریم و آن را در دسته ویزیت شده قرار می‌دهیم.
  3. تمام گره‌هایی که همسایه گره ویزیت شده هستند و هنوز ویزیت نشده‌اند را در آخر صف قرار می‌دهیم.
  4. مراحل 2 و 3 را تا زمانی که صف خالی شود، تکرار می‌کنیم.

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

حال با یک مثال نحوه کارکرد الگوریتم جستجوی اول سطح یا BFS را بررسی می‌کنیم.

نمونه ای از یک گراف که قرار است الگوریتم BFS روی آن اجرا شود

با گره 0 شروع می‌کنیم. الگوریتم، این گره را در دسته گره‌های ویزیت شده قرار می‌دهد و تمام گره‌های همسایه آن ‌که گره‌های 1، 2 و 3 هستند را به صف منتقل می‌کند.

ویزیت کردن گره ی صفر

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

ویزیت کردن گره یک

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

ویزیت کردن گره دو

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

ویزیت کردن گره سه

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

ویزیت کردن گره چهارم و خالی ضدن صف

پیاده‌سازی الگوریتم جستجوی اول سطح

Pseudo Code

شبه کد الگوریتم BFS در زیر نشان داده شده است:

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
  remove the head u of Q 
  mark and enqueue all (unvisited) neighbours of u

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

Python

# BFS algorithm in Python

import collections

# BFS algorithm
def bfs(graph, root):

  visited, queue = set(), collections.deque([root])
  visited.add(root)

  while queue:

    # Dequeue a vertex from queue
    vertex = queue.popleft()
    print(str(vertex) + " ", end="")

    # If not visited, mark it as visited, and
    # enqueue it
    for neighbour in graph[vertex]:
      if neighbour not in visited:
        visited.add(neighbour)
        queue.append(neighbour)

if __name__ == '__main__':
  graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
  print("Following is Breadth First Traversal: ")
  bfs(graph, 0)

Java

// BFS algorithm in Java

import java.util.*;

public class Graph {
  private int V;
  private LinkedList<Integer>adj[];

  // Create a graph
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i  v; ++i)
      adj[i] = new LinkedList();
  }

  // Add edges to the graph
  void addEdge(int v, int w) {
    adj[v].add(w);
  }

  // BFS algorithm
  void BFS(int s) {

    boolean visited[] = new boolean[V];

    LinkedList<Integer> queue = new LinkedList();

    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
      s = queue.poll();
      System.out.print(s + " ");

      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }

  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, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");

    g.BFS(2);
  }
}

C

// BFS algorithm in C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue {
  int items[SIZE];
  int front;
  int rear;
};

struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node {
  int vertex;
  struct node* next;
};

struct node* createNode(int);

struct Graph {
  int numVertices;
  struct node** adjLists;
  int* visited;
};

// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
  struct queue* q = createQueue();

  graph->visited[startVertex] = 1;
  enqueue(q, startVertex);

  while (!isEmpty(q)) {
    printQueue(q);
    int currentVertex = dequeue(q);
    printf(“Visited %d\n”, currentVertex);

    struct node* temp = graph->adjLists[currentVertex];

    while (temp) {
      int adjVertex = temp->vertex;

      if (graph->visited[adjVertex] == 0) {
        graph->visited[adjVertex] = 1;
        enqueue(q, adjVertex);
      }
      temp = temp->next;
    }
  }
}

// Creating a node
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// Creating a graph
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));
  graph->visited = malloc(vertices * sizeof(int));

  int I;
  for (i = 0; i adjLists[i] = NULL;
    graph->visited[i] = 0;
  }

  return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
  // Add edge from src to dest
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  // Add edge from dest to src
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

// Create a queue
struct queue* createQueue() {
  struct queue* q = malloc(sizeof(struct queue));
  q->front = -1;
  q->rear = -1;
  return q;
}

// Check if the queue is empty
int isEmpty(struct queue* q) {
  if (q->rear == -1)
    return 1;
  else
    return 0;
}

// Adding elements into queue
void enqueue(struct queue* q, int value) {
  if (q->rear == SIZE – 1)
    printf(“\nQueue is Full!!”);
  else {
    if (q->front == -1)
      q->front = 0;
    q->rear++;
    q->items[q->rear] = value;
  }
}

// Removing elements from queue
int dequeue(struct queue* q) {
  int item;
  if (isEmpty(q)) {
    printf(“Queue is empty”);
    item = -1;
  }
  else {
    item = q->items[q->front];
    q->front++;
    if (q->front > q->rear)
    {
      printf(“Resetting queue “);
      q->front = q->rear = -1;
    }
  }
  return item;
}

// Print the queue
void printQueue(struct queue* q) {
  int I = q->front;

  if (isEmpty(q)) {
    printf(“Queue is empty”);
  }
  else {
    printf(“\nQueue contains \n”);
    for (i = q->front; i items[i]);
    }
  }
}

int main() {
  struct Graph* graph = createGraph(6);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 2);
  addEdge(graph, 1, 4);
  addEdge(graph, 1, 3);
  addEdge(graph, 2, 4);
  addEdge(graph, 3, 4);

  bfs(graph, 0);

  return 0;
}

C++

// BFS algorithm in C++

#include <iostream>
#include <list>

using namespace std;

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

  public:
  Graph(int vertices);
  void addEdge(int src, int dest);
  void BFS(int startVertex);
};

// Create a graph with given vertices,
// and maintain an adjacency list
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
}

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

// BFS algorithm
void Graph::BFS(int startVertex) {
  visited = new bool[numVertices];
  for (int i = 0; i < numVertices; i++)
    visited[i] = false;

  list<int> queue;

  visited[startVertex] = true;
  queue.push_back(startVertex);

  list ::iterator I;

  while (!queue.empty()) {
    int currVertex = queue.front();
    cout  “Visited “  currVertex  “ “;
    queue.pop_front();

    for (I = adjLists[currVertex].begin(); I != adjLists[currVertex].end(); ++i) {
      int adjVertex = *I;
      if (!visited[adjVertex]) {
        visited[adjVertex] = true;
        queue.push_back(adjVertex);
      }
    }
  }
}

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

  g.BFS(2);

  return 0;
}

پیچیدگی زمانی و فضایی الگوریتم جستجوی اول سطح

از آن‌جایی که در بدترین حالت، جستجوی اول سطح باید همه مسیرها را به تمام گره‌های ممکن در نظر بگیرد، پیچیدگی زمانی جستجوی اول سطح برابر با $\mathrm{O}\left(\left|\mathrm{E}\right|\mathrm{+}\left|\mathrm{V}\right|\right)$ است که در آن $\left|\mathrm{V}\right|$ و $\left|\mathrm{E}\right|$ کاردینالیته یا تعداد اعضای مجموعه رئوس و یال‌ها به ترتیب است. همچنین، از آن‌جایی که همه گره‌های یک سطح باید ذخیره شوند تا زمانی که گره‌های فرزندشان در سطح بعدی تولید شوند، پیچیدگی فضایی متناسب با تعداد گره‌ها در عمیق‌ترین سطح است. پیچیدگی فضایی را می‌توان به صورت $\mathrm{O}\left(\left|\mathrm{V}\right|\right)$ نیز بیان کرد که در آن $\left|\mathrm{V}\right|$ کاردینالیته مجموعه رئوس است. در بدترین حالت، گراف عمق 1 دارد و تمام رئوس باید ذخیره شوند.

کاربردهای الگوریتم جستجوی اول سطح

مزایای جستجوی اول سطح

جستجوی اول سطح مزایای بسیاری دارد که از بین آنها می‌توان به موارد زیر اشاره کرد:

معایب جستجوی اول سطح

اشکال اصلی BFS نیاز آن به حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوترحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم است. از آن‌جایی که هر سطح از نمودار باید ذخیره شود تا سطح بعدی تولید شود و مقدار حافظه متناسب با تعداد گره‌های ذخیره شده است، پیچیدگی فضایی جستجوی اول سطح از مرتبه $\mathrm{O}\left(\mathrm{bd}\right)$ است، که b ضریب انشعاب است (تعداد فرزندان در هر گره) و d عمق است. در نتیجه، BFS در عمل به شدت محدود به فضا است، بنابراین حافظه موجود در رایانه‌های معمولی را در عرض چند دقیقه تمام می‌کند.

جمع‌بندی

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

الگوریتم جستجوی اول سطح (Breadth First Search) یا BFS چیست؟

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

DFS بهتر است یا BFS؟

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

کاربردهای BFS چیست؟

BFS در سیستم‌های GPS برای یافتن مکان‌های همسایه استفاده می‌شود. در شبکه، زمانی که می‌خواهیم چند بسته را پخش کنیم، از الگوریتم BFS استفاده می‌کنیم. الگوریتم مسیریابی بر اساس BFS یا DFS است. BFS در الگوریتم فورد-فولکرسون برای یافتن حداکثر جریان در یک شبکه استفاده می‌شود.

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

در پیاده‌سازی‌های استاندارد ،BFS از ساختمان داده صف استفاده می‌شود.

محدودیت های الگوریتم BFS چیست؟

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

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