mafulechka
mafulechkaШілде 16, 2019, 5:03 Т.Ж.

Бірінші іздеу кеңдігі (BFS)

Саяхат графиктің барлық түйіндеріне баруды білдіреді. Бірінші кеңдікке өту немесе алдымен кеңдік іздеу — графиктің немесе ағаш деректер құрылымының барлық шыңдарын іздеуге арналған рекурсивті алгоритм. Бұл мақалада сіз C++, C, Java және Python бағдарламаларында іске асырылған BFS алгоритмі, BFS псевдокоды және BFS алгоритм кодының мысалдарын көресіз.


BFS алгоритмі

BFS стандартты орындалуы әрбір график шыңын екі санаттың біріне қояды:

  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

#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 коды

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 или где?

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз