Поиск в глубину на С

Следующим идет поиск в глубину или обход дерева в глубину или же DFS, реализация на Си. Реализация будет не рекурсивная, с использованием очереди из предыдущего поста.

Немного информации из вики:

Поиск в глубину

Поиск в глубину (англ.Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

 

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

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 dfs(tree_node_t * root, visit_node_f node_function, void *visit_data)
{
    list_t *st = create_list();

    list_push(st, root);

    while(st->size != 0) {
        tree_node_t * node = st->head->data;
        /* посетить вершину, если это не сделали раньше */
        if(node->mark != 1){
            (*node_function)(node, visit_data);
            node->mark = 1;
        }

        if(node->left != NULL && !node->left->mark) {
            list_push(st, node->left);
            continue;
        }

        if(node->rigth != NULL && !node->rigth->mark) {
            list_push(st, node->rigth);
            continue;
        }
        /* Извлекаем обработанную вершину из стека */
        tree_node_t * rel_node = (tree_node_t *)list_pop(st);
    }

    free(st);
}

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>