如何使用 BFS 算法指示生成树的先序
我正在用 C++ 实现 BFS 算法来查找生成树，生成树的输出应该按预序显示，但我对实现有疑问，如果不完全知道如何构建树，我该如何构建树每个节点都有很多孩子？考虑递归树结构 树的数据结构可以写为：
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);
}
我还想知道是否有任何方法可以在不使用树结构的情况下对节点进行预序。
I'm doing an implementation of the BFS algorithm in c++ to find a spanning tree, the output for a spanning tree should be shown in preorder, but I have a doubt in the implementation, how I can build a tree if not exactly know how many children have each node?. Considering a tree structure recursive The data structure of the tree can be written as:
typedef struct node
{
int val;
struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.
But do not think it works this implementation as mentioned before.
This is my function to return the tree in preorder:
void preorder(tree t)
{
if(t == NULL)
return;
printf("%d ", t->val);
preorder(t->left);
preorder(t->right);
}
I also wonder if there is any way to do the preorder of the nodes without using a tree structure.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我在帖子中看到了两个具体问题：
left指针视为指向第一个子级的指针，将right指针视为指向下一个同级的指针。由于图的广度优先搜索隐式地构建了生成树，因此如果您实际上以某种方式表示它，则可以按预序遍历该树。稍微扩展一下第二点：树的预序遍历仅意味着每个节点在其子节点之前被处理。当您进行图搜索时，您想要遍历图的连接组件，仅访问每个节点一次，您就可以有效地创建一棵隐式树。也就是说，您的起始节点成为树的根节点。每当您访问一个节点时，您都会搜索尚未访问过的相邻节点，即未标记的节点。如果存在这样的节点，则关联边将成为树节点并标记该节点。由于总是只有一个节点被主动持有，因此您需要记住未处理的节点，但是，在某些数据结构中，例如堆栈或队列（而不是显式地使用堆栈，您可以执行递归来创建隐式堆栈）。现在，如果您在第一次看到节点时发出节点号，那么您显然会在其子节点之前处理它，即您最终会按照预序遍历的顺序写入节点号。
如果你不明白这一点，请拿出一张纸画一个图形和一个队列：
选择一个节点作为搜索的起始节点，该节点与树的根节点相同。将其编号写入队列中的第一个空位置并标记即填充该节点。现在继续搜索：
现在队列矩形包含由广度优先隐含的生成树的前序遍历图形的搜索。使用较粗的线可以看到生成树。如果您将队列的矩形视为堆栈，该算法也将起作用，但它会有点混乱，因为您最终会在仍待处理的节点之间找到已勾选的节点：而不是查看第一个未勾选的节点，而是查看第一个未勾选的节点最后一个未勾选的节点。
在使用图算法时，我发现可视化算法非常有帮助。虽然让计算机来维护绘图固然很好，但在纸上绘制东西并可能通过许多标记的铅笔指示活动节点的低技术替代方案即使不是更好，也同样有效。
只是对代码的评论：每当您读取任何输入时，请确保成功读取数据。顺便说一句，您的代码显然只是 C 而不是 C++ 代码：可变长度数组在 C++ 中不可用。在 C++ 中，您将使用
std::vector; followOrder(vertexNumber) 而不是int followOrder[vertexNumber]。有趣的是，该代码也不是 C 语言，因为它使用例如std::queue。I have seen two concrete questions in the posting:
leftpointer to be a pointer to the first child and therightpointer to point to the next sibling. Since breadth first search of a graph implicitly builds up a spanning tree, you can then walk this tree in preorder if you actually represent it somehow.To expand a bit on the second point: a preorder walk of a tree just means that each node is processed prior to it child nodes. When you do a graph search you want to traverse through a connected component of a graph, visiting each node just once, you effectively create an implicit tree. That is, your start node become the root node of the tree. Whenever you visit a node you search for adjacent nodes which haven't been visited, i.e. which isn't marked. If there is such a node, the incident edge becomes a tree node and you mark the node. Since there is always only just one node being actively held you need to remember the nodes which aren't processed, yet, in some data structure, e.g. a stack or a queue (instead of using a stack explicitly you could do recursion which creates the stack implicitly). Now, if you emit the node number the first time you see a node you clearly process it prior to its children, i.e. you end up writing the node number the order of a preorder walk.
If you don't understand this, please whip out a sheet of paper and draw a graph and a queue:
Now choose a node to become the start node of your search which is the same as the root node of your tree. Write its number into the first empty position in the queue and mark i.e. fill the node. Now proceed with the search:
Now the queue rectangle contains a preorder walk of the spanning tree implied by a breadth first search of the graph. The spanning tree is visible using the thicker lines. The algorithm would also work if you treated the rectangle for the queue as a stack but it would be a bit messier because you end up with ticked off nodes between nodes still to be processed: instead of looking at the first unticked node you would look at the last unticked node.
When working with graph algorithms I found it quite helpful to visualize the algorithm. Although it would be nice to have the computer maintain the drawing, the low-tech alternative of drawing things on paper and possibly indicating active nodes by a number of labeled pencils works as well if not better.
Just a comment on the code: whenever you are reading any input, make sure that you successfully read the data. BTW, your code is clearly only C and not C++ code: variable length arrays are not available in C++. In C++ you would use
std::vector<int> followOrder(vertexNumber)instead ofint followOrder[vertexNumber]. Interestingly, the code isn't C either because it uses e.g.std::queue<int>.