如何使用算法BFS指示生成树的预订 [英] How to indicate preorder of a spanning tree using the algorithm BFS

问题描述

我在c ++中执行BFS算法来找到一个生成树，生成树的输出应该以预订的形式显示，但我在实现中有疑问，如果没有确切知道每个节点有多少个孩子？考虑树结构递归树的数据结构可以写成：

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.

推荐答案

我在帖子中看到了两个具体问题：

I have seen two concrete questions in the posting:

1. 是否可能有一个数据结构在树中使用两个以上的孩子？当然这是可能的。有趣的是，它甚至可能与您发布的节点结构！只需考虑 left 指针是指向第一个子节点的指针，而 right 指向下一个兄弟节点。因为广度优先搜索图形会隐含地建立一个生成树，所以如果你实际上以某种方式表示它，你就可以预先遍历这棵树。


2. 你可以不使用树结构体？是的，这也是可能的。基本上，DFS和BFS在概念上没有什么不同：你只是有一个数据结构保持下一个要访问的节点。对于DFS，这是一个堆栈，对于BFS，这是一个队列。如果您在将数据结构插入到要访问的节点的数据结构中时发出节点编号，您将获得树的预订步骤（即，访问父节点之后的所有子节点）。

1. Is it possible to have a data structure using more than two children in a tree? Of course this is possible. Interestingly, it is even possible with the node structure you posted! Just consider the left pointer to be a pointer to the first child and the right pointer 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.
2. Can you do a preorder walk without using a tree structure? Yes, this is possible, too. Essentially, DFS and BFS are conceptually no different for this: you just have a data structure maintaining the nodes to be visited next. For DFS this is a stack, for BFS this is a queue. You get a preorder walk of the tree (i.e. you visit all children of a node after the parent) if you emit the node number when you insert it into the data structure maintaining the nodes to be visited.

要扩展第二点上的位：预先遍历树仅仅意味着每个节点在其子节点之前被处理。当您执行图搜索时，要遍历图的连接组件，只需访问每个节点一次，就可以有效地创建一个隐式树。也就是说，您的起始节点成为树的根节点。每当您访问节点时，您搜索未被访问的相邻节点，即未被标记的节点。如果存在这样的节点，则入射边缘变为树节点，并且您标记该节点。因为总是只有一个节点被主动地保持，所以需要记住未被处理的节点，然而在某些数据结构中，例如，堆栈或队列（而不是显式地使用堆栈，你可以做递归，隐式创建堆栈）。现在，如果你第一次看到一个节点，你会在它的子节点之前清楚地处理节点号，也就是说，你最终将节点号写入预订节点的顺序。

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.

  只需对代码进行注释：每当您读取任何输入时，请确保成功读取数据。 BTW，你的代码显然只是C而不是C ++代码：变长数组在C ++中不可用。在C ++中，你将使用 std :: vector< int> followOrder（vertexNumber）而不是 int followOrder [vertexNumber] 。有趣的是，代码不是C，因为它使用例如。 std :: queue< int> 。

  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 of int followOrder[vertexNumber]. Interestingly, the code isn't C either because it uses e.g. std::queue<int>.

  这篇关于如何使用算法BFS指示生成树的预订的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！