Поиск в ширину на С

Следующим за поиском в глубину идет поиск в ширину или BFS. Так как и в случае поиска в глубину, реализация будет итеративной, с использованием реализованной ранее очереди.

Немного инфы из вики:

поиск в ширину

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска[1].

 

Будем использовать структуру данных из прошлого поста:

typedef struct tree_node {
    /* указатель на левую вершину */
    struct tree_node * left;
    /* указатель на правую вершину */
    struct tree_node * rigth;
    /* указатель на хранимые в вершине данные */
    void *data;
    /* необходимая при обходе пометка */
    int mark;
} tree_node_t;

Так же нужно определить указатель на функцию которая быдет вызывается для обработки данных находящихся в обрабатываемой вершине.

typedef void (*visit_node_f)(tree_node_t *node, void *visit_data);

Т.е. нам нужно определить функцию которая будет проводить некоторые манипуляции с данными хранимыми в вершине tree_node_t *node, а void * data будет расшариваться между всеми вызовами, например в нем можно сохранить счетчик или еще что-нибудь что может пригодиться при обработке данных.

 

А теперь сам алгоритм:

 

void bfs(tree_node_t * root, visit_node_f node_function, void *visit_data)
{
    list_t *st = create_list();

    list_push_back(st, root);

    /* Посещаем корневую вершину */
    (*node_function)(root, visit_data);
    root->mark = 1;

    while(st->size != 0) {
        tree_node_t * node = (tree_node_t *)list_pop(st);

        if(node->left != NULL && !node->left->mark){
            list_push_back(st, node->left);
            /* посещаем левую вершину */
            (*node_function)(node->left, visit_data);
            node->left->mark = 1;

        }

        if(node->rigth != NULL && !node->rigth->mark){
            list_push_back(st, node->rigth);
            /* посещаем правую вершину вершину */
            (*node_function)(node->rigth, visit_data);
            node->rigth->mark = 1;
        }
    }
}

Вот и все.

dreamway89

dreamway89 wrote 29 posts

Post navigation


Добавить комментарий

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>