Как указать предварительный заказ связующего дерева с использованием алгоритма BFS

Question

Я выполняю реализацию алгоритма BFS в C++, чтобы найти связующее дерево, вывод для связующего дерева должен отображаться в предварительном порядке, но у меня есть сомнения в реализации, как я могу построить дерево, если точно не знаю, сколько детей имеет каждый узел ?. Учитывая структуру дерева рекурсивных структура данных дерева можно записать в виде:

typedef struct node 
{ 
     int val; 
     struct node *left, *right; 
}*tree; //tree has been typedefed as a node pointer. 

Но не думаю, что это работает эта реализация, как упоминалось ранее.

Это моя функция возвращает дерево в предзаказа:

void preorder(tree t) 
{ 
     if(t == NULL) 
       return; 
     printf("%d ", t->val); 
     preorder(t->left); 
     preorder(t->right); 
} 

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

Answer 1

Я видел два конкретных вопросов в проводке:

1. Можно ли иметь структуру данных с использованием более двух детей в дереве? Конечно, это возможно. Интересно, что это возможно даже с созданной вами структурой узлов! Просто рассмотрите указатель left как указатель на первый ребенок и указатель right, чтобы указать на следующего брата. Поскольку ширина первого поиска графа неявно создает связующее дерево, вы можете пройти это дерево в предзаказе, если вы его каким-то образом представляете.
2. Можете ли вы сделать предварительный заказ без использования древовидной структуры? Да, это тоже возможно. По сути, DFS и BFS концептуально не отличаются для этого: у вас есть только структура данных, поддерживающая последующие посещения узлов. Для DFS это стек, для BFS это очередь. Вы получаете предварительный ход дерева (т. Е. Вы посещаете всех дочерних узлов узла после родителя), если вы испускаете номер узла, когда вы вставляете его в структуру данных, поддерживая посещаемые узлы.

Чтобы расширить немного на второй точке: а предзаказ ходьбы дерева просто означает, что каждый узел обрабатывается до него дочерних узлов. Когда вы выполняете поиск по графу, который хотите пройти через подключенный компонент графа, посещая каждый узел только один раз, вы фактически создаете неявное дерево. То есть ваш начальный узел становится корневым узлом дерева. Всякий раз, когда вы посещаете узел, вы ищете соседние узлы, которые не были посещены, т. Е. Которые не отмечены. Если есть такой узел, фронт инцидента становится узлом дерева, и вы отмечаете узел. Поскольку всегда активен только один узел, вам необходимо запомнить узлы, которые не обрабатываются, но в некоторой структуре данных, например. стек или очередь (вместо того, чтобы явно использовать стек, вы можете сделать рекурсию, которая неявно создает стек). Теперь, если вы испускаете номер узла, первый раз, когда вы видите узел, который вы четко обрабатываете его перед его дочерними элементами, т. Е. Вы в конечном итоге записываете номер узла в порядок прогона предварительного заказа.

Если вы не понимаете этого, пожалуйста, выхватить лист бумаги и нарисовать график и очередь:

• узлы с полыми кругами и число их узлов рядом с ними
• края с тонкими линиями
• очередь только прямоугольники, которые не содержат ничего в начале

Теперь выбирают узел, чтобы стать начальным узлом вашего поиска, который является таким же, как корневым узел вашего дерева. Запишите его номер в первую пустую позицию в очереди и отметьте i.e.заполните узел. Теперь приступают с поиском:

• взгляда на узле, указанный в начале очереди и найти соседний узел, который не заполнен:
  • добавляемого узел на заднюю очереди (т.е. сразу за последний узел в прямоугольнике)
  • знак (т.е. заполнения) узел
  • сделать линии, соединяющей два узла толще: он не является деревом края в настоящее время
• если нет дополнительно немаркированных смежно узлы отмечают передний узел в очереди (т. е. удалите его из очереди) и перейдите к следующему узлу до тех пор, пока не появятся дополнительные узлы

Теперь прямоугольник очереди содержит предварительный ход остовного дерева, подразумеваемый широким первым поиском графа. Облицовочное дерево видно с помощью более толстых линий. Алгоритм также работал бы, если бы вы рассматривали прямоугольник для очереди как стек, но это было бы немного беспорядочно, потому что в конечном итоге вы удалили узлы между узлами, которые еще предстоит обработать: вместо того, чтобы смотреть на первый неуправляемый узел, вы должны смотреть на последний unticked узел.

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

Просто комментарий к коду: всякий раз, когда вы читаете какие-либо данные, убедитесь, что вы успешно прочитали данные. Кстати, ваш код явно только C, а не код C++: массивы переменной длины недоступны в C++. В C++ вы должны использовать std::vector<int> followOrder(vertexNumber) вместо int followOrder[vertexNumber]. Интересно, что код не является C, потому что он использует, например. std::queue<int>.