Должен ли я использовать библиотеку графиков?

Я делаю DFS и BFS решатель для лабиринта.

У меня нет знаний (в значительной степени плачевных знаний) о том, как реализовать Graph в C ++ и как реализовать узлы, которые будут иметь несколько дочерних элементов, в зависимости от того, сколько смежных ячеек пусто.

Я искал дни для дружественного для начинающих способа реализовать граф в C ++. В прямом смысле. Дни.

Все, что я нашел, было слишком сложным для меня, я нашел только продвинутые вещи, которые не мог понять. Самый дружелюбный сайт для начинающих, который я нашел, это этот но в этом он использует C и даже реализует стек, который, как я верю в C ++, уже есть класс Stack. Даже этот сайт мне трудно понять.

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

Я загружаю библиотеку наддува, когда набираю ее, поэтому, если я решу использовать библиотеку, я, вероятно, воспользуюсь этой.

Поэтому я никогда не должен учиться создавать графы и узлы и просто использовать библиотеку наддува (или любую другую в этом отношении), или существуют ли действительно удобные для начинающих способы научиться создавать графы и узлы для алгоритма DFS и особенно для лабиринта?

3

Решение

Поскольку DFS и BFS являются тривиальными алгоритмами, нет необходимости получать их из библиотеки. Да, они реализованы в BGL но эта библиотека в первую очередь для более сложных алгоритмов. Кроме того, BGL предоставляет некоторые представления графов, но на самом деле реализован таким образом, что вы можете использовать собственную структуру данных графиков и при этом применять алгоритмы BGL. Но по-другому: реализуйте график и алгоритмы самостоятельно!

Для DFS и BFS реализация графика довольно проста, так как вам даже не нужен отдельный тип ребер (нет дополнительных данных, сохраняемых для ребер за пределами того места, на которое они указывают). Для реализации графика вам понадобится узел тип, который хранит флаг (чтобы указать, был ли узел посещен) и контейнер с индикаторами целевых узлов. Чаще всего контейнер просто хранит указатели на целевой узел, что, конечно, означает, что узлы, на которые он указывает, остаются в памяти.

Вы можете использовать либо std::deque<Node> если вы только добавляете / удаляете узлы на одном из концов или std::list<Node> если вы можете добавлять / удалять узлы в любом месте графика (для реализации DFS и BFS вы только добавляете узлы, которые можно сделать в конце, то есть я бы пошел с std::deque<Node>). Внутри узлов вы бы просто сохранили std::vector<Node*>, Вставляя ребро между двумя узлами, вы просто находите два узла и добавляете указатель на исходный узел. std::vector<Node*> к цели Node, Если график не является ненаправленным, вы бы добавили указатели на std::vector<Node*> обоих узлов.

Кстати, я бы не назвал DFS или BFS «искусственным интеллектом». Кроме того, кажется, что вы ищете решение C ++, то есть тег C тоже кажется неуместным.

2

Другие решения

Кажется, вам не нужно реализовывать узел как сложную структуру.
В случае, когда узел представляет собой просто ячейку лабиринта, вы можете использовать целые числа для идентификации конкретной ячейки.

В случае, если размер лабиринта равен MxN, у вас будет массив узлов MxN длины.

Чтобы представить отношение смежности между узлами, вы можете использовать матрицу смежности (что нормально в случае достаточно маленьких графов) или списки смежности (что более эффективно в вашем случае, потому что каждый узел может иметь 4 или меньше смежных узлов).

Вы можете легко найти информацию о соседстве в Google.

Итак, это тот случай, когда вам действительно не нужно ничего сложного, чтобы реализовать эти алгоритмы.
Вам понадобятся только массивы (но действительно лучше использовать векторный контейнер из STL) и контейнер очереди из STL для BFS (DFS использует стек, но вы можете использовать рекурсию, которая явно использует стек).

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector