mafulechka
mafulechka16 июля 2019 г. 5:03

Поиск в ширину (Breadth first search, BFS)

Обход означает посещение всех узлов графа. «Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье вы познакомитесь с примерами алгоритма BFS, псевдокода BFS и кодом алгоритма «поиска в ширину» с реализацией в программах на C ++, C, Java и Python.


Алгоритм BFS

Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий:

  1. Посещенные.
  2. Не посещенные.

Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов.

Алгоритм работает следующим образом:

  1. Начните с размещения любой вершины графа в конце очереди.
  2. Возьмите передний элемент очереди и добавьте его в список посещенных.
  3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в конец очереди.
  4. Продолжайте повторять шаги 2 и 3, пока очередь не опустеет.

Граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм BFS на каждом узле.

Пример BFS

Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.

Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.

Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.

У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.

В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.

Поскольку очередь пуста, мы завершили обход в ширину графика.

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

Код для алгоритма «поиска в ширину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.

BFS в 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;
};
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);
void bfs(struct Graph* graph, int startVertex);
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;
}
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;
       }
    }
}

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

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 < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }

    return graph;
}

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;
}
struct queue* createQueue() {
    struct queue* q = malloc(sizeof(struct queue));
    q->front = -1;
    q->rear = -1;
    return q;
}
int isEmpty(struct queue* q) {
    if(q->rear == -1) 
        return 1;
    else 
        return 0;
}
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;
    }
}
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;
}
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 < q->rear + 1; i++) {
                printf("%d ", q->items[i]);
        }
    }    
}

BFS в C++

#include <iostream>
#include <list>

using namespace std;

class Graph
{
    int numVertices;
    list *adjLists;
    bool* visited;
public:
    Graph(int vertices);  
    void addEdge(int src, int dest); 
    void BFS(int startVertex);
};

Graph::Graph(int vertices)
{
    numVertices = vertices;
    adjLists = new list[vertices];
}

void Graph::addEdge(int src, int dest)
{
    adjLists[src].push_back(dest);
    adjLists[dest].push_back(src);
}

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

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

BFS Java код (Java code)

import java.io.*;
import java.util.*;

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

    Graph(int v)
    {
        numVertices = v;
        visited = new boolean[numVertices];
        adjLists = new LinkedList[numVertices];
        for (int i=0; i i = adjLists[currVertex].listIterator();
            while (i.hasNext())
            {
                int adjVertex = i.next();
                if (!visited[adjVertex])
                {
                    visited[adjVertex] = true;
                    queue.add(adjVertex);
                }
            }
        }
    }

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

BFS в Python

import collections
def bfs(graph, root): 
    visited, queue = set(), collections.deque([root])
    visited.add(root)
    while queue: 
        vertex = queue.popleft()
        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]} 
    breadth_first_search(graph, 0)
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Вам это нравится? Поделитесь в социальных сетях!

s
  • 6 декабря 2021 г. 9:51
 for (int i=0; i i = adjLists[currVertex].listIterator();

это foreach или где?

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
B

C++ - Тест 002. Константы

  • Результат:16баллов,
  • Очки рейтинга-10
B

C++ - Тест 001. Первая программа и типы данных

  • Результат:46баллов,
  • Очки рейтинга-6
FL

C++ - Тест 006. Перечисления

  • Результат:80баллов,
  • Очки рейтинга4
Последние комментарии
k
kmssr9 февраля 2024 г. 5:43
Qt Linux - Урок 001. Автозапуск Qt приложения под Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
АК
Анатолий Кононенко5 февраля 2024 г. 12:50
Qt WinAPI - Урок 007. Работаем с ICMP Ping в Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
EVA
EVA25 декабря 2023 г. 21:30
Boost - статическая линковка в CMake проекте под Windows Ошибка LNK1104 часто возникает, когда компоновщик не может найти или открыть файл библиотеки. В вашем случае, это файл libboost_locale-vc142-mt-gd-x64-1_74.lib из библиотеки Boost для C+…
J
JonnyJo25 декабря 2023 г. 19:38
Boost - статическая линковка в CMake проекте под Windows Сделал всё по-как у вас, но выдаёт ошибку [build] LINK : fatal error LNK1104: не удается открыть файл "libboost_locale-vc142-mt-gd-x64-1_74.lib" Хоть убей, не могу понять в чём дел…
G
Gvozdik19 декабря 2023 г. 8:01
Qt/C++ - Урок 056. Подключение библиотеки Boost в Qt для компиляторов MinGW и MSVC Для решения твой проблемы добавь в файл .pro строчку "LIBS += -lws2_32" она решит проблему , лично мне помогло.
Сейчас обсуждают на форуме
P
Pisych27 февраля 2023 г. 15:04
Как получить в массив значения из связанной модели? Спасибо, разобрался:))
AC
Alexandru Codreanu19 января 2024 г. 22:57
QML Обнулить значения SpinBox Доброго времени суток, не могу разобраться с обнулением значение SpinBox находящего в делегате. import QtQuickimport QtQuick.ControlsWindow { width: 640 height: 480 visible: tr…
BlinCT
BlinCT27 декабря 2023 г. 19:57
Растягивать Image на парент по высоте Ну и само собою дял включения scrollbar надо чтобы был Flickable. Так что выходит как то так Flickable{ id: root anchors.fill: parent clip: true property url linkFile p…
Дмитрий
Дмитрий10 января 2024 г. 15:18
Qt Creator загружает всю оперативную память Проблема решена. Удалось разобраться с помощью утилиты strace. Запустил ее: strace ./qtcreator Начал выводиться весь лог работы креатора. В один момент он начал считывать фай…
Evgenii Legotckoi
Evgenii Legotckoi12 декабря 2023 г. 17:48
Побуквенное сравнение двух строк Добрый день. Там случайно не высылается этот сигнал textChanged ещё и при форматировани текста? Если решиать в лоб, то можно просто отключать сигнал/слотовое соединение внутри слота и …

Следите за нами в социальных сетях